a) T(n) = T(√n) + Θ(lg lg n)
Solution: Change of variables: let m = lg n. Recurrence becomes
S(m) = S(m/2) + Θ(lg m).
Case 2 of master’s theorem applies, so T(n) = Θ((lg lg n)^2).
b) T(n) = T(n -2) + lg n
Solution: T(n) = Θ(n log n). This is T(n) = Pn/2
i=1 lg 2i ≥
Pn/2
i=1 lg i ≥ (n/4)(lg n/4) =
Ω(n lg n). For the upper bound, note that T(n) ≤ S(n), where S(n) = S(n-1)+lg n,
which is clearly O(n lg n).
d) T(n) = √n T(√n) + 100n
Solution: Master’s theorem doesn’t apply here directly. Pick S(n) = T(n)/n. The
recurrence becomes
S(n) = S(√n) + 100. The solution of this recurrece is S(n) = Θ(lg lg n).
(You can do this by a recursion tree, or by substituting m = lg n again.)
Therefore, T(n) = Θ(n lg lg n).