The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
306 views
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
+1

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.

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

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).
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
190,487 comments
85,106 users