# Questions tagged [master-theorem]

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

198 questions
Filter by
Sorted by
Tagged with
1 vote
28 views

### Recurrence Upper Bound Estimation

I'm going through CLRS and was trying to solve for the asymptotic bound of the following recurrence (exercise 4-5.4) $$T(n) = 4T(n/2) + n^2\text{lg }n$$ According to CLRS definition of Master Theorem, ...
47 views

### Does the Master Theorem apply to T(n) = 3T(n/3) + n/log2(n)?

Id say this is the first case of Master Theorem, but when I try to prove that the limit of f(n)/ n ^ (1-E) is 0, I cannot do it. Does anyone have a solution?
1 vote
106 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 ...
46 views

### Big O notation of T(n) = T(n/2) + O(log n) using master theorem?

I am aware that the algorithm has 1 recursive call of size n/2 and the non-recursive part takes O(log n) time. Master theorem formula is T(n) = aT(n/b) + O(n^d). In this case a = 1, b = 2, but I am ...
29 views

1 vote
22 views

### Is this a special case of a recurrence where the Master Method is not applicable?

So in an exam, this was the recurrence: $$T(n) = 2T(n/2) + n log(n) -n + O(log(n))$$ $$T(1) = 1$$ Why does the master method not apply here? I think it is indeed int he form $$aT(n/b) + f(n)$$ You ...
1 vote
106 views

### Complexity of recursive function using Master theorem

this code aims to determine whether there exists a contiguous subarray starting from index 0 in the given array A whose elements sum up to the target value S. can we apply Master theorem to find out ...
1 vote
31 views

1 vote
187 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 ...
38 views

### find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$

We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and assume $T(1)$ is a constant. Find asymptotically tight bounds $\Theta(f(n))$ for $T(n)$. There's something that confuses me. We ...
66 views

1k views

67 views

### Solve the recurrence $3T(n) = T(n/3)+ \sqrt{\log n}$

How can you solve the recurrence $$3T(n) = T(n/3)+ \sqrt{\log n}$$ using the master theorem? I am lost in this question.
1 vote
121 views

### Big theta and big 0 bounds for iteration method and Master Theorem

In Algorithms 1, I'm noticing that big-Theta running times are always used for recurrence relations when using the iteration method. Meanwhile, using the Master Theorem always seems to result in a big-...
200 views

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

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

### Regularity condition for cases 1 & 2

My question concerns the version of the Master Theorem described in CLRS and in this handout. I already understand the following: If the regularity condition in case 3 does not hold, then we can't ...
568 views

### How to solve $T(n) = 27T(n/9) + n^3$ with substitution method

I'm trying to bound this recurrence with the substitution method. My guess is $O(n^3)$. These are some steps: $$T(n) \leq cn^3 \\ T(n) \leq 27cn^3+n^3$$ How can I continue?
1 vote
154 views

### Why doesn't master theorem solve $T(n) = 2T(n/2) + n\lg\lg n$?

Given two recurrences: $T(n) = 2 T(n/2) + n \lg \lg n$ $T(n) = 4 T(n/2) + n \lg \lg n$ I'd think that both works for master theorem, but the solution is that the first one cannot use masters ...
1 vote
### 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}$ ?