Recurrence: How to approach

Question

Solve Recurrence

A) T(n) = T( √ n) + Θ(lg lg n)

B) T(n) = T(n/2 + √ n) + √ 6046

C) T(n) = T(n − 2) + lg n

D) T(n) = √ n T( √ n) + 100n

Comments

Well.. if you are expecting to solve it by Master-Method then its not possible. Because it does not fit into the generic form : 

a possible way to solve this is by Substitution method. Substitute thrice(3 times is enough) to identify some pattern.

---

Cab we use the approach like take n=(n/2)^2..so equation 1 will we like T(n)<=T(n/2)+lg n/2...and solve it using master method.....is this the right approach...

---

by that method you'll make mistakes, as you have already started to do the same, So better go for substitution method.

Answer 1

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).