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
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
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
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
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
11 votes
1 answer
2k views

Intuition behind the Master Theorem

The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following: For a recurrence ...
roctothorpe's user avatar
  • 1,158
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
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
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
6 votes
1 answer
917 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 ...
Alex ten Brink's user avatar
6 votes
1 answer
2k views

Applying the Master Theorem on Merge sort

I found the proof below in a textbook. I would like to know why it is important for the proof that it uses $\lceil \frac{n}{2} \rceil$ instead of just $\frac{n}{2}$? I know that you can't split into ...
Natasha's user avatar
  • 61
6 votes
1 answer
178 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: ...
Luc Peetersen's user avatar
6 votes
1 answer
2k views

Cases of Master Theorem

Suppose that we have $ \\ T(n)=\left\{\begin{matrix} c, & \ \text{if } n<d\\ aT\left( \frac{n}{b} \right )+f(n), & \ \ \text{if } n \geq d \end{matrix}\right.$ The Master theorem is the ...
Mary Star's user avatar
  • 431
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
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
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
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
5 votes
1 answer
6k views

What is the case 2 in master theorem?

I am confused about the statement of the Master theorem in CLRS book. Here is the link of the book CLRS. In page 94, the theorem, in case 2, states that: If $\displaystyle f(n)=\Theta(n^{\log_ba})$,...
Kira's user avatar
  • 53
5 votes
1 answer
2k views

Finding recurrence when Master Theorem fails

Following method is explained by my senior. I want to know whether I can use it in all cases or not. When I solve it manually, I come to same answer. $T(n)= 4T(n/2) + \frac{n^2}{\lg n}$ In above ...
avi's user avatar
  • 1,463
5 votes
1 answer
5k views

Meaning of polynomially larger or smaller in the context of the master method

I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
Trixie the Cat's user avatar
4 votes
2 answers
1k views

Does T(n) = 2 · T(2n) + n apply to Master method?

I'm trying to apply the master method to the following recurrence: $$T(n) = 2 \cdot T(2n)+n.$$ We have $a=2$ and $b=1/2$. Also, $f(n)=n$ and $n^{\log_b a} = n^{\log_{1/2} 2} = n^{-1}$ since $\log_{1/2}...
Jarvis's user avatar
  • 109
4 votes
2 answers
748 views

Usage of master theorem for solving recursions

I know that master theorem is used for the recurrence relations of the form: T(n) = aT(n/b) + f(n) But in my question, i am supposed to solve the following recurrence relation by using master ...
bigO's user avatar
  • 91
4 votes
1 answer
600 views

Master Method to solve recurrences is 'a' related to 'b'?

The master method allows us to solve certain recurrences of the form $$T(n) = aT(n/b)+f(n)\,,$$ where $a\ge1$ and $b>1$ are constants and $f(n)$ is a positive function with some further ...
Onkar N Mahajan's user avatar
4 votes
1 answer
3k views

Conditions for applying Case 3 of Master theorem

In Introduction to Algorithms, Lemma 4.4 of the proof of the master theorem goes like this. $a\geq1$, $b>1$, $f$ is a nonnegative function defined on exact powers of b. The recurrence relation for $...
Jia Cheng Sun's user avatar
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
4 votes
1 answer
2k views

Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n

For analyzing the running time of an algorithm , I'm stuck with this recursive equation : $$ T(n) = \log(n) \cdot T(\log n) + n $$ Obviously this can't be handled with the use of the Master Theorem, ...
Ashkan Kazemi's user avatar
4 votes
5 answers
30k views

Solving T(n) = 3T(n/3)+n/2 using master method

I thought I understood the Master Method quite well till I saw this question $T(n) = 3T(\frac{n}{3})+\frac{n}{2}$ My approach: $a = 3 ; b=3$ and $f(n) = \frac{n}{2}$ $n^{\log_b{a}}$ = $n^{log_3{...
WizCrack's user avatar
3 votes
5 answers
44k views

How to solve T(n)=2T(√n)+log n with the master theorem?

I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?
Nimbus9000's user avatar
3 votes
4 answers
85 views

Asymptotic Runtime of Interrelated Functions

I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me... How would I find the asymptotic ...
recursion.ninja's user avatar
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
2 answers
593 views

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Given the recurrence $$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$ My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
Bender's user avatar
  • 367
3 votes
1 answer
7k views

Master theorem for $T(n)=T(n-1)+O(n)$

The recurrence of selection sort is $$T(n) = T(n-1)+ O(n).$$ Can we apply the master theorem to this recurrence? I am confused because the master theorem can be applied to the following recurrence $$...
blockByblock's user avatar
3 votes
2 answers
8k views

How do we derive the runtime cost of Karatsuba's algorithm?

I've read the Wikipedia article explaining the complexity analysis of the Karatsuba algorithm, but I'm not fully grasping it. I seem to have gotten about 75% of the way to the solution on my own, but ...
Josiah's user avatar
  • 161
3 votes
2 answers
534 views

Formulating the master theorem with Little-O- and Little-Omega notation

In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this: Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \...
Emily's user avatar
  • 133
3 votes
3 answers
3k views

Master Theorem: How to find the value of b in this recurrence relation

The master theorem is used with recurrences of the form T(n) = aT(n/b) + f(n) where a >=1 and b > 1, in which case the value of b can be easily seen from the ...
EvaD's user avatar
  • 31
3 votes
1 answer
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)^...
Toda Raba's user avatar
  • 133
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
3 votes
2 answers
220 views

$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$

I'm trying to prove that for arbitrary $c > 0$, $f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$ Intuitively, this seems to be true to me (little-o implies ...
John Doe's user avatar
3 votes
2 answers
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)$ ...
Vahagn Babajanyan's user avatar
3 votes
1 answer
255 views

Time complexity of tree algorithm

I'm new to recurrence relations and master theorem so trying to learn. Say there's an algorithm $A$ whose input is the root of a binary tree $T$. $A$ recurses so that it's called on each and every ...
onepiece's user avatar
  • 133
3 votes
1 answer
215 views

Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$

Find the asymptotic bound in terms of $\Theta$ (Theta) using the master theorem for the following recursive equation. Assume that $t(n)= \Theta (1)$ for suffucuently small $n$. $$t(n)=t(\frac{n}{...
Bshara Zahran's user avatar
3 votes
1 answer
405 views

Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem?

Wikipedia says that the following recurrence is inadmissible since there is a non-polynomial difference between $f(n) = \frac{n}{\log n}$ and $n^{\log_b a}$: $$ T(n) = 2T\left(\frac{n}{2}\right) + \...
Olórin's user avatar
  • 859
3 votes
1 answer
6k views

Does Master Theorem apply to $T(n) = 4T(n/2) + n^2 \log n$

Based on CLRS Theorem 4.1, master theorem doesn't apply to $T(n) = 4T(n/2) + n^2 \log n$. However, I saw the 4th condition of master theorem on slides of Bourke. If $f(n)=\Theta(n^{\log_ba}\log^kn)$, ...
Dan's user avatar
  • 43
3 votes
1 answer
550 views

Clarification of the proof involving the regularity condition in Master Theorem

I was going the text Introduction to Algorithms by Cormen et al. Where I came across the following statement in the proof of the third case of the Master's Theorem. (The Statement of Master theorem) ...
Abhishek Ghosh's user avatar
3 votes
1 answer
193 views

Is there a difference between using $n$ and $\Theta(n)$ in recurrences?

Is there a difference between $T(n)=2T(n/2)+n$ and $T(n)=2T(n/2)+Θ(n)$ when using the master theorem? I've seen it both ways and am a little confused. (Looking for the answer $nlogn$).
Hello's user avatar
  • 169
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
1 answer
2k views

Applying Case 3 of Master Theorem to $T(n) = 9T(n/3) + n^3$

Given $T(n) = 9T(n/3) + n^3$, I know that $a =9$, $b=3$, and $f(n) = n^3$ and $n^{\log_{3}9} = n^2$ thus Case 3 applies: $n^{\log_{b}a} < f(n)$, $n^2 < n^3$. Can someone explain how to apply the ...
dairyknight86's user avatar
3 votes
1 answer
481 views

Compare two complexity functions having the same asymptotic complexity

For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found: $A1: T_{A1}(n)=4n^2 +7log(n^2)$ $A2: T_{A2}(n) = 4T(n/2) + log(n)$ Say, technically ...
ddon-90's user avatar
  • 169
2 votes
1 answer
889 views

Merge sort: sorting and merging complexity $\Theta(n)$

So this is the Master theorem for Merge Sort: $$ T(n) = 2T(n/2) + \Theta(n). $$ I am not able to understand why is the time complexity for sorting and merging $\Theta(n)$. Is sorting $O(1)$ and ...
Arjun Hegde's user avatar
2 votes
2 answers
10k views

What is the recurrence form of Bubble-Sort

I understand how bubble sort works and why it is O(n^2) conceptually but I would like to do a proof of this for a paper using the master theorem. As an example: The recurrence form for merge sort is ...
pseudo's user avatar
  • 21