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.

The Gateway to Computer Science Excellence

+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

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

+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 :

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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,727 answers

199,451 comments

107,856 users