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
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 ...
Raphael's user avatar
  • 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 ...
seeker's user avatar
  • 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 ...
newprint's user avatar
  • 461
11 votes
2 answers
21k 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 $...
Joachim's user avatar
  • 213
6 votes
2 answers
25k views

$T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]

According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why? And which case of master theorem is it?
user16715's user avatar
5 votes
3 answers
15k views

Solving recurrence relation with square root

I am trying to solve the following recurrence relation :- $T(n) = T(\sqrt{n}) + n$ using masters theorem. We can substitute $n = 2 ^ m$ $T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$ Now we can rewrite it ...
Zephyr's user avatar
  • 993
4 votes
1 answer
946 views

Master Theorem and rounding up to the nearest integer

For the master theorem for recurrences of the form $$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)\,,$$ what difference would it make if the split was into calls of $\lceil n/b\rceil$ instead of $n/...
Barry S's user avatar
  • 43
6 votes
0 answers
219 views

Are there master theorems that deal with parameters of the form $n-c$?

While thinking about this question on a recurrence I checked out some stronger master theorems. Unfortunately, they do not seem to apply because terms $\qquad\displaystyle T(n) = \dots + T(n-1) + \...
Raphael's user avatar
  • 72.4k
5 votes
2 answers
752 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)...
sam's user avatar
  • 339
2 votes
1 answer
69 views

Could I apply the master theorem if my $N/b$ is $\varphi(N)$?

Let $$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$ where $\varphi(N)$ is Euler's totient function. Can I somehow express $\...
R. Chopin's user avatar
  • 237
19 votes
3 answers
22k 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 ...
user avatar
16 votes
3 answers
13k 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 ...
Laura's user avatar
  • 534
9 votes
2 answers
1k views

Why does Akra-Bazzi need that toll-function g is bounded?

Following up on vonbrand's answer I want to write a small document about stronger master theorems for our students, one of which is the Akra-Bazzi theorem. I have copied the theorem from their paper [...
Raphael's user avatar
  • 72.4k
5 votes
1 answer
2k views

How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

Consider the recurrence $$T(n)= 4T(\sqrt n) + \log^2n. $$ I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
shashank jaiswal's user avatar
3 votes
1 answer
234 views

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, when $f(n)$ is oscillating). Suppose, however, that $f(n)$ is ...
Maiaux's user avatar
  • 155
3 votes
2 answers
31k views

Solution to recurrence $T(n) = T(n/2) + n^2$

I am getting confused with the solution to this recurrence - $T(n) = T(n/2) + n^2$ Recursion tree - ...
codeomnitrix's user avatar
3 votes
1 answer
202 views

Justifying a claim in the proof of the master theorem

I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true. My argument is as follows: Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\...
random_0620's user avatar
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 ...
Vincent Nivoliers's user avatar
2 votes
1 answer
93 views

Run time of a Simple Recurrence

Given the recurrence $T(n) = T(\sqrt{n}) + \theta(lglgn)$, provide an asymptotically tight bound on it's run time. My solution was to let $m = 2\sqrt{n}$, which leads to the recurrence $S(m) = S(m/2) ...
japata's user avatar
  • 123
1 vote
2 answers
166 views

Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction

We have this recurrence: $$T(n)=10T(\frac{n}{3})+n\sqrt{n}.$$ We can solve it using Master Theorem and say it is $\Theta(n^{\log_3{10}})$. I want to prove it using induction but I don't know the ...
Mason Rashford's user avatar
1 vote
1 answer
332 views

Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?

I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence ...
Ilya Loskutov's user avatar
0 votes
1 answer
6k views

Does the master theorem apply to T(n) = 3T(n/3) + nlogn?

I am given an example of a case where the master theorem does not apply, but it seems like it should apply. This was the reasoning: $T(n) = 3T(n/3) + n \log n$ with $ a = 3, b=3, f(n) = n\log n$ ...
pajkatt's user avatar
  • 141
0 votes
2 answers
70 views

What's an upper bound for this recurrence so I can take advantage of the Master Theorem?

Let $$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + 2T(\sqrt{N}) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$ where $\varphi(N)$ is Euler's totient function. My ...
R. Chopin's user avatar
  • 237
0 votes
1 answer
3k views

Solving $T(n) = 3T(\frac{n}{3})+\sqrt{n}$ using master method

How can I use the master's method in order to solve the recurrence formula $T(n)=3T(\frac{n}{3})+\sqrt{n}$ ?
Rako Maristella's user avatar