# Questions tagged [master-theorem]

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

24 questions
Filter by
Sorted by
Tagged with
20 votes
1 answer
1k views

### Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ...
• 72.4k
18 votes
5 answers
23k views

### Solving a recurrence relation with √n as parameter

Consider the recurrence $\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$ for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$. I know the Master theorem for ...
• 283
9 votes
2 answers
31k views

### Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence $$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$ by applying the Master Theorem. I am ...
• 461
11 votes
2 answers
21k views

• 43
6 votes
0 answers
219 views

• 339
2 votes
1 answer
69 views

• 133
2 votes
1 answer
711 views

### Regularity condition in the master Theorem in the presence of Landau notation for f

There already are many questions and answers about the importance of the regularity condition in case 3 of the Master Theorem. My question is about when can we safely assume the regularity condition ...
2 votes
1 answer
93 views