CS 215 Homework 1
Due Friday Week 2

1. Write a θ(n) algorithm that sorts n distinct integers ranging in size between 1 and kn inclusive, where k is a constant positive integer. (Hint: use a kn-element array.) You may submit your answer in pseudocode or code.
2. What is the time complexity of the code fragment below? For simplicity, you may assume that n is a power of 2. Don't just write down a function; you must explain your answer.

   for (i = 1; i <= n; i++)
   {
       j = n; 
       while (j >= 1) 
       {
           // body of the while loop    // requires θ(1) time
           j = ⌊j/2⌋
       }
   }
   

3. What is the time complexity of the code fragment below? For simplicity, you may assume that n is a power of 2. Don't just write down a function; you must explain your answer.

   i = n;
   while (i >= 1)
   {
       j = i; 
       while (j <= n)
       {
           // body of while loop   // requires θ(1) time
           j = j * 2;
       }
       i = ⌊i/2⌋
   }
   

4. Prove that for any functions f(n) and g(n), if f(n) = θ(g(n)), then g(n) = θ(f(n)).

5. For each of these statements, decide if it is true or false. If the statement is true, then prove it. (To prove it you will need to use the definition and find constants to make it work.) If the statement is false, then give a reason or a counterexample.
   1. 10n² ∈ O(n³).
   2. n² ∈ Ω(n³).
   3. 2ⁿ ∈ θ(2ⁿ⁺¹).
   4. n! ∈ θ((n+1)!)
   5. What does O(1) mean? θ(1)?