Questions tagged [master-theorem]

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

Filter by
Sorted by
Tagged with
20
votes
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 ...
3
votes
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)$ ...
0
votes
1answer
166 views

Explanation of a specific recurrence with respect to Master Theorem

Concerning the Master Theorem. I have found the following equation as the base of analysis: $\quad T(n) = aT(n/b) + \Theta(n^k)$ but I also found the following: $\quad T(n) = aT(n/b) + \Theta(...
18
votes
5answers
20k 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 ...
1
vote
1answer
4k views

Big Omega of $n \log n$

While studying master method at recurrences topic I'm stacked at a point. It is written in the book as: $T(n) = 3T(n/4) + n \log n$, we have $a = 3, b = 4$, $f(n) = n \log n$, and $...
5
votes
2answers
636 views

Problems showing the constraint of master theorem case three holds

Prove or disprove the following statements: $T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \theta \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right)...
16
votes
2answers
17k views

Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
8
votes
2answers
17k 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 ...
6
votes
1answer
175 views

Finding lambda of Master Theorem

Suppose I have a recurrence like $T(n)=2T(n/4)+\log(n)$ with $a=2, b=4$ and $f(n)=\log(n)$. That should be case 1 of the Master theorem because $n^{1/2}>\log(n)$. There is also a lambda in case 1: ...
11
votes
2answers
18k views

Master theorem not applicable?

Given the following recursive equation $$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that $$ n^{\log_2(2)} = n.$$ Now we check the first two cases for $...
15
votes
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 ...
6
votes
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 ...
3
votes
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)^...

1 2 3
4