# Questions tagged [master-theorem]

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

163 questions
Filter by
Sorted by
Tagged with
1answer
903 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 ...
2answers
2k views

### How to the examples for using the master theorem in Cormen work?

I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples $3T( \frac{n}{4} ) + n\log(n)$ $2T( \frac{n}{2} ) + n\log(n)$ ...
1answer
166 views

2answers
636 views

3answers
8k views

### Solving Recurrence Equations containing two Recursion Calls

I am trying to find a $\Theta$ bound for the following recurrence equation: $$T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42$$ I figure Master Theorem is inappropriate due to differing amount of ...
1answer
818 views

### Master theorem and constants independent of $n$

I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version): $$T(n)=4T(n/2)+O(r)$$ $r$ is independent of $n$. Case 1 of the Master theorem applies ...
1answer
2k views

### Solve a recurrence using the master theorem

This is the recursive formula for which I'm trying to find an asymptotic closed form by the master theorem: $$T(n)=9T(n/27)+(n \cdot \lg(n))^{1/2}$$ I started with $a=9,b=27$ and \$f(n)=(n\cdot \lg n)^...