COMP-4540/8540
Design and Analysis of Algorithms
Winter 2022
Assignment 1
Due Date: February 17 (before 11:59p.m.)
1. Prove that for any k > 0, nk ∈ o(2
√
n).
2. Prove that Θ(f) ∩ o(f) = ∅.
3. Prove or disprove.
Let f, g : N→ R+ ∪ {0} and h : R+ ∪ {0} → R+ ∪ {0}.
If f(n) ∈ O(g(n)), then h(f(n)) ∈ O(h(g(n))).
4. Rank the following functions by order of growth; i.e. find an ordering g1, g2, . . . , g7 of the functions such
that gi ∈ o(gi+1) or gi ∈ Θ(gi+1), for 1 ≤ i < 7. Partition the list into equivalences classes such that
functions f(n) and g(n) are in the same class if and only if f(n) = Θ(g(n)). Provide proofs.
nlg lgn, (n+ 1)!, (lg n)!, en, nlgn, n+ (lg n)lgn, 22
lg lgn+1
[Hint: n! = Θ((n
e
)n
√
n) (Stirling’s formula)]
5. Solve the following recurrences:
(a) T (n) = 3T (n
2
) + n2 lg3 n+ 2n
(b) T (n) = 3T (n
3
) +
√
lg n
(c) T (n) = 8T (n
4
) + n
√
n lg2 n
6. Solve the recurrence T (n) = T (n
2
+ 5) + n2.
1