Skip to main content

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
1 vote
1 answer
3k views

Master Theorem Case 3 Regularity Condition

In case 3 of the master theorem, we have to show that $$ af(n/b) \leq cf(n). $$ I don't understand how I can setup this formula. As an example, we have $$ T(n)=3T(n/4) + n \lg n.$$ In this ...
Carlo's user avatar
  • 15
1 vote
2 answers
2k views

Using the Master theorem on a recurrence with non-constant a

I am trying to solve the following equation using master's theorem. $T(n) = 3^n T(\frac{n} 3) + O(1)$ Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what ...
Steph's user avatar
  • 37
-2 votes
1 answer
85 views

Time complexity of a Divide and Conquer

I have Master theorem for finding complexities but the problem is Master theorem says For a recurrence of form $T(n) = aT(n/b) + f(n)$ where $a \geq 1$ and $b > 1$, there are following three cases:...
iankit3's user avatar
2 votes
1 answer
69 views

Master method recurrence question [duplicate]

This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified $f(n)$ (as denoted below). For a recurrence of $$T(n) = a T(\frac{n}{b}) +...
D. Johnson's user avatar
1 vote
2 answers
817 views

Non-integer $a$ in Master method

According to CLRS the master method requires the recurrence to be of form $T(n) = aT(n/b) + f(n)$ where $a \ge 1 $ and $b > 1$ are constants and $f(n)$ is asymptotically positive. This makes it ...
ljleppan's user avatar
  • 113
1 vote
1 answer
36 views

How do I get the solution for a recursion with n! using Master Theorem?

The problem in my book is T(n) = 16T(n/4) + n! I don't know how to get at the correct solution my book has, which says Θ(n!) here are pictures of the master theorem and the problem in my book.
eric's user avatar
  • 11
0 votes
1 answer
795 views

How to deal with $n\sqrt n$ in master theorem?

In classifying the following formula's asymptotic complexity using master theorem, I have $a = 8$, $b = 4$, and $d = ?$ $T(n) = 8T(n/4) + n\sqrt n$ How do I handle $n\sqrt n$ in this case to get $d$ ...
ThisClark's user avatar
  • 113
2 votes
1 answer
372 views

Understanding Master Method's Case 2

Whats the intuition behind multiplying the factor $\log n$ Master Method Case 2 (CLRS Section 4.5) If $f(n) = \theta(n^{\log_b a})$, then $T(n)= \theta(n^{\log_b a} \log n)$ In generalized ...
Atinesh's user avatar
  • 749
-3 votes
1 answer
385 views

time complexity analysis of recurrence relation [duplicate]

I am not able to solve time complexity analysis of this recurrence relation: T(n)=3T(n/2)+n^2.I want to find time complexity analysis of this recurrence relation without using masters theorem could ...
mahendra'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
0 votes
0 answers
30 views

Solving $T(n)=2T(n/2) + n \lg n$ , For ex: Counting inversions implemented with full mergesort [duplicate]

How to solve the recurrence equation $T(n)=2T(n/2) + n \lg n$ For ex: I implemented "Counting inversions" with a full mergesort instead of just using merge part, So the outer complexity will be $n \...
coder000001's user avatar
5 votes
1 answer
7k 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
1 vote
2 answers
464 views

Reccurence of recursive function with unequal sizes of subproblems [duplicate]

Given pseudocode: ...
Basti Funck'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
0 votes
0 answers
40 views

why this recurrence can be solved by Master method? [duplicate]

I have studied the following recurrence. The ratio between f(n) and n^log_b(a) is log n so there is non polynomial difference but I have studied from book that it can be solved by master method. $T (...
user4129542's user avatar
0 votes
1 answer
151 views

Solving a recurrence relation using Divide and Conquer Master Theorem [duplicate]

For the recurrence relation $$T(n) = 16T(n/4) + n!\,,$$ I have found that $T(n)\in Θ(n!)$. Can this be deduced using the Master Theorem?
Rahul Chittimalla's user avatar
1 vote
1 answer
177 views

What kind of recurrence relations has p < 0?

By the master method, $T(n) = aT(\frac {n}{b})+\Theta(n^k\log^pn)$ where $p$ is real. I know $\log^4n=\log(\log(\log(\log n)))$ but how do you calculate something like $\log^pn$ where $p<0$?
Siddharth Thevaril'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
-1 votes
1 answer
199 views

Master Theorem Questions?

NOTE: I asked this on mathstackexchange, but didn't get the responses I wanted, thought I should post in CS. Sorry if i did something wrong but i am a newbie. State the asymptotic (worstcase) ...
duvalgup22's user avatar
-1 votes
1 answer
1k views

Satisfying all the conditions of case 3 of the Master Method except the regularity condition

The regularity condition of case 3 of Master Method says that $af(n/b) < cf(n)$, for $c < 1$. How to devise a recurrence relation that satisfies all other conditions of case 3 except the ...
rrrocky's user avatar
  • 149
4 votes
1 answer
601 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
-1 votes
1 answer
341 views

A difficult master theorem problem

Consider the function $B:\mathbb{N}\rightarrow\mathbb{R}$ defined by $$ B(n) = \begin{cases} 1 &\text{if $n\le 2$}\\ B\left(\left\lceil\frac{n}{\log_2n}\right\rceil \right)+n&...
John's user avatar
  • 11
-1 votes
1 answer
63 views

Is my analysis of this recurrence relation correct?

The following recurrence relation, $$T(n)=16T(\frac{n}{4}) + n^2$$ has been given to me to be solved via the Master Theorem. I'm pretty sure this is a case 2 situation, since $$\log_4{16} = 2$$ and ...
blissfreak's user avatar
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
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
32k 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
0 votes
1 answer
2k views

Master theorem for $T(n) = 2T(n/2) + n^{2}\log n$

Would I use the third case of the Master Theorem for the recurrence equation $T(n) = 2T(n/2) + n^{2}\log n$? The condition given for the third case by Wikipedia is $f(n) = \Theta(n^c)$ when $c > \...
Voltemand11's user avatar
6 votes
0 answers
220 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.6k
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.6k
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
-1 votes
1 answer
630 views

Solving a recurrence with the Master Theorem

Problem taken from here (page 3): http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-Handout.pdf $T(n) = 3T(\frac{n}{2}) + \frac{3}{4}n + 1$ $f(n) = \frac{3}{4}n + 1$ It says we cannot use ...
user2666425's user avatar
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
2 votes
2 answers
136 views

Not sure if my solution to following recurrence is correct

I have a recurrence relation, it is like the following: $T(e^n) = 2(T(e^{n-1})) + e^n$, where $e$ is the base of the natural logarithm. To solve this and find a $\Theta$ bound, I tried the following:...
yrazlik's user avatar
  • 151
0 votes
0 answers
32 views

The use of master theorem appriopriately [duplicate]

I have a recurrence relation and trying to use master theorem to solve it. The recurrence relation is: $T(n) = 3T(n/5) + n^{0.5}$ Can I use the master theorem in that relation? If so, can I say that ...
yrazlik's user avatar
  • 151
4 votes
2 answers
750 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
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.6k
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
0 votes
1 answer
171 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(...
Cratylus's user avatar
  • 101
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
2 votes
1 answer
5k 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 $...
user avatar
5 votes
2 answers
754 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
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
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
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
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
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
  • 544
6 votes
1 answer
919 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
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

1 2 3
4