# Questions tagged [master-theorem]

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

163 questions
Filter by
Sorted by
Tagged with
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 ...
1answer
46 views

### What is the asymptotic bound for $T(n)= 3T(\sqrt{n})+n^3$?

What is the asymptotic bound? How do you get to the result? $$T(n)= 3 \cdot T(\sqrt{n})+n^3$$
1answer
62 views

### Relaxing hypotheses of Master Theorem

This question is related to 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,...
1answer
42 views

### Using inductive hypothesis on recurrence relation?

I have a recurrence relation as follows $$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$ Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor ...
2answers
58 views

1answer
37 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)$, ...
1answer
50 views

### Recurrence relations and the Master Theorem

Although it might be a bit of newbie question, my question is, How can I apply the Master theorem to the following relation: T(n) = 99T(n/100) + log(n!) I'm trying ...
1answer
175 views

### Solving $T(n) = 4T(n/2) + n^3$ with substituton method

I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, ...
1answer
33 views

### How to prove $T(n) = 2T(n/2) + n/\log(n)$ can't be solved using the Master Theorem?

I have read (in this question) that this recursion can't be solved via Master Theorem. But I couldn't find exact and complete proof why the Master Theorem does not apply.
1answer
46 views

### Intuition on O(number of leaves) for master theorem

I am trying to develop the intuition of the master theorem for the case where $a > b^{d}$ [Case 3] in this video. In the video, they say that since most of the work is done at the leaves, we should ...
1answer
40 views

### Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$

I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$ with base case $T(n) = 1$ if $n \leq 1$. I am sure that the Master Theorem does not work. I am trying a lot with ...
2answers
82 views

### Solving T(n) = 2*T(n-1)+4 witht the Master Theorem

I am wondering if there is a way to solve a recurrence time function with the master theorem if no $b$ exists. Like in this case. $$T(n) = 2\times T(n-1)+4$$
1answer
248 views

### Solving $T(n) = 16T(n/2) + n$

I am trying to solve the following recurrence relation :- $T(n)=16T(n/2)+n$ using masters theorem. I got $\Theta (n^2)$ (Which matched the first case in the theory) which is wrong, any help with this ...
1answer
322 views

0answers
33 views

### Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...