# Questions tagged [master-theorem]

Questions on the Master theorem, a method for obtaining asymptotic bounds on recurrences of a specific form.

198 questions
Filter by
Sorted by
Tagged with
75 views

• 23
1 vote
921 views

• 113
1 vote
172 views

### Proving van Emde Boas recurrence

I have tried to solve the following question: van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$. ...
101 views

### Relaxing hypotheses of Master Theorem

This question is related to Master Theorem on oscillating function. Consider a recurrence of the form $T(n) = a T(n/b) + f(n)$ Master Theorem's regularity condition excludes some cases (for example,...
• 954
87 views

### Recurrence : $T(n) = 4T(n/2) + Θ(n^2/\log n)$

Is there a way to solve this recurrence using master theorem: $$T(n) = 4T(n/2) + Θ(n^2/\log n)$$
35 views

128 views

### Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...
• 177
1 vote
428 views

### How to use master theorem to solve $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$

I want to solve the following using master theorem. $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$ I have: $a=4, b=8,f(n)=\sqrt n (\log_2 n)^2$ I calculate $n^{log_b a} = n^{\log_8 4} = n^{2/3}$ I ...
• 177
181 views

### Solve recurrence with Master Theorem - Polynomially Smaller/Larger

The problem is to solve the recurrence using Master Theorem : $$T(n) = 2T(n/2)+\log_2 {n}$$ My attempt: $$a=2, b=2, f(n)= \log_2 {n}, g(n)=n^{\log_b{a}}=n$$ I am torn between case 1 & the ...
42 views

• 111
508 views

1 vote