The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
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
in Algorithms by Active (4.6k points)
edited by | 306 views

Well.. if you are expecting to solve it by Master-Method then its not possible. Because it does not fit into the generic form : T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n)  \;\;\;\; \mbox{where} \;\; a \geq 1 \mbox{, } b > 1

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)^ equation 1 will we like T(n)<=T(n/2)+lg n/2...and solve it using master 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.

1 Answer

0 votes
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 ≥


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).
ago by (11 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,984 questions
55,135 answers
85,106 users