Sample problems for tutorial #2

1. Rank the following functions by order of growth. That is, order them so that f₁ ∈ O(f₂), f₂ ∈ O(f₃), etc. Make sure to indicate whether or not f_i ∈ Θ(f_i+1). For instance you could use the notation n < n^2 = 2n^2 < n^4...

   n3 - n √ n	n!	log (log n)	1.01n
   √ n log n	17	4913n289	32n-17
   1.011.01n	√ n	3n	nn
   n18/17	n log17 n	32n	n3 + log n

2. Prove that for each fixed value of k > 0, 1^k + 2^k + ... + (t-1)^k + t^k ∈ Θ(t^k+1). Hint: do not use induction. Instead, treat k as a constant, and do O and Ω separately. You will need to apply a trick we learned in class to deal with Ω.
3. Analyze the running time of the following algorithm as a function of n, assuming that each arithmetic operations takes constant time. Use O, Ω or Θ notation as appropriate to express your result as simply and as precisely as possible. Give an informal argument (not necessarily a full proof) to support your answer.

   Algorithm Strange(n)
       sum ← 0
       while (n > 3) do
           sum ← sum + n
           if (n is even) then
               n ← n / 2
           else
               n ← n + 3
           endif
       return sum