Tutorial #2 Problems

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 O(n) ⊂ O(n^2) = O(2n^2) ⊂ O(n^4)...

n³ – n √ n
n! log (log n) 1.01ⁿ

√ n log n
17 4913n²⁸⁹ 3^2n-17

1.01^1.01ⁿ √ n
3ⁿ nⁿ

n^18/17 n log¹⁷ n 3²ⁿ n³ + log n
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. (Remember that for Ω bounds, it is legal to drop positive terms and reduce the size of positive terms, since you can guarantee that the resulting function is still a lower bound on the original.)
Analyze the running time of the following algorithm as a function of n, assuming that each arithmetic operation 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. (It may help to think about the “measure of progress” approach the book used to analyze the while loop in the Gale-Shapley Algorithm.)
```
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
```

Archived CPSC 320 2014W2 Website