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
2
votes
1answer
81 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) ...
0
votes
2answers
2k views

Applicabilty of master theorem (case 1) for T(n)=9T(n/3)+nlogn

I want to know if the recurrence equation $T(n) = 9T(\frac{n}{3}) + nlogn$, can or cannot be solved using master theorem. At first, I naively went for $O(n^2)$ applying case 1 of master theorem. But ...
1
vote
1answer
107 views

Finding any $\epsilon$ vs finding minimal $\epsilon$ for case 3 of Master theorem

I have a recurrence relation: $$T(n) = 3T(\frac{n}{4}) + n\lg n$$ and I want to prove that $T(n) = \Theta(f(n))$ using Master theorem. There's also an example in my textbook on this relation, they're ...
1
vote
1answer
362 views

Solving recurrence relations using substitution followed by tree method/masters theorem

$T(n) = 4T(\sqrt n) + n$ First I substitute n = $2^k$: $T(2^k) = 4T(2^{k/2}) + 2^k$ Now I rename the above as follows: $S(k)=4S(k/2) + 2^k$ Now if I try to use tree method on this in the ...
3
votes
3answers
2k 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 ...
4
votes
5answers
15k 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{...
1
vote
3answers
2k views

Meaning of the constants that appear in the Master Theorem

The general formula for time complexity is $T(n) = aT(n/c) + bn^k$. If $a> c^k$, the complexity is $O(n^{\log_c a})$. If $a = c^k$, it is $O(n^k \log n)$. If $a < c^k$, it is $O(n^k)$. $a$ is ...
6
votes
1answer
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 ...
0
votes
0answers
9 views

Need Help solving Recurrence Problem [duplicate]

I have this practice problem that I was given. I am trying to solve a specific recurrence equation T(n) = 4 when n <= 2 T(n) = 3T(n/3) + 5 when n > 2 ...
4
votes
1answer
626 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/...
2
votes
3answers
297 views

Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n

The questions is to find the running time $T(n)$ of the following function: $$T(n)=3\cdot T(n/2) + n \tag{1}$$ I know how to solve it using Master theorem for Divide and Conquer but I am trying to ...
0
votes
4answers
3k views

Applying Master Theorem to: T(n) = T(n - 2) + n^2 [duplicate]

I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation: T(n) = T(n-2) ...
0
votes
0answers
13 views

Does master theorem apply differently for $n$ with restrictions? [duplicate]

Given $T(1) = 1$ and $T(n) = 4T(n/2) +n^2$ for $n\geq 2$, can I solve the recurrence for $T$ by applying the master theorem with $a = 4$, $b = d = 2$? This would give $T(n) = \Theta(n^2\log n)$.
1
vote
1answer
3k views

Solving using the master theorem [duplicate]

I am wondering why this $T(n)=3T(n/4)+n⋅lg(n)$ recurrence can be solve by Master Theorem case 3 but this $T(n)=2T(n/2)+n⋅lg(n)$ recurrence can not be solve by Master Theorem what is the difference ...
1
vote
1answer
56 views

Not convincing claim for Master Theorem Case 3

In a practice exam given in class, we were asked to solve the following recurrence $$T(n) = 2T(n/4) + \frac{n}{\log n}$$ The given solution claims that this falls in the third case of the Master ...
1
vote
1answer
2k 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 ...
1
vote
2answers
1k 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 ...
-2
votes
1answer
77 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:...
2
votes
1answer
68 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}) +...
1
vote
2answers
382 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 ...
1
vote
1answer
29 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.
0
votes
1answer
456 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$ ...
1
vote
1answer
64 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 ...
-3
votes
1answer
378 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 ...
5
votes
1answer
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 ...
0
votes
0answers
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 \...
4
votes
1answer
2k 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})$,...
1
vote
2answers
374 views
3
votes
2answers
6k 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 ...
0
votes
0answers
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 (...
0
votes
1answer
124 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?
1
vote
1answer
176 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$?
3
votes
1answer
350 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) + \...
-1
votes
1answer
170 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) ...
-2
votes
1answer
689 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 ...
4
votes
1answer
557 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 ...
-1
votes
1answer
294 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&...
-1
votes
1answer
62 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 ...
5
votes
2answers
19k 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?
3
votes
4answers
78 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 ...
3
votes
2answers
18k 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 - ...
0
votes
1answer
849 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 > \...
6
votes
0answers
205 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) + \...
8
votes
2answers
978 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 [...
4
votes
1answer
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, ...
-1
votes
1answer
588 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 ...
5
votes
1answer
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 ...
2
votes
2answers
117 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:...
0
votes
0answers
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 ...
4
votes
2answers
459 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 ...