# Questions tagged [master-theorem]

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

182 questions
Filter by
Sorted by
Tagged with
36 views

### Understanding Master Theorem

Someone who was explaining to me the master theorem said that for the case 1, we compare the $n^{log_b(a)}$ and $f(n)$. If the growth rate of $n^{log_b(a)}$ is greater than the growth rate of $f(n)$ ...
• 101
29 views

141 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
58 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 ...
• 11
83 views

### Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?

The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
89 views

### How to solve $T(n) = 2T(n/4) + n \log n$ with substitution method?

I am trying to solve this recurrence with substitution method. I guess $T(n) = \Theta(n \log n)$ (with Master Theoreme). Can someone show me how to demonstrate the upper bound $T(n) = O(n \log n)$?
1 vote
52 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 ...
• 21
49 views

### How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
1 vote
144 views

### Master Method: Divide and Conquer

According to my evaluation ,the overall asymptotic running time of the below algorithm is O(n) ,since x (number of recursive ...
45 views

### recurrence with exponentials

I am trying to figure out on how to approach the problem on finding proving the asymptotic of an exponential recurrence. It is described as such: t(n)=4t(n/2)+2^n with t(1)=1 for n>=5 From what I ...
• 1
107 views

### Total work done at a recursion tree level

In the proof of Master theorem in Dasgupta's Algorithms the author says that the total work done at a recursion tree level is $$a^k \times O\left(\frac{n}{b^k}\right)^d$$ where $a$ is the branching ...
• 123
142 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$$
461 views

### How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?

Can somebody help me with this recurrence please? $T(n)=4T(\sqrt{n}/3)+(\log n)^2$
1 vote
137 views

### Solving constants in the recursive term with master theorem

We are learning how to solve recurrence relations in different ways (Forward Substitution, Backward Substitution, Master Theorem, etc...). I really thought I understood the topic since most of the ...
• 13
75 views

### Divide and conquer recurrence relation

I have divide and conquer problem and below is the recurrence relation for it \begin{align}t (n) &= a\cdot t (n/4) + O (n^2/\log(n)) + O(n^2)\\ t(n) &= a\cdot t (n/4) + O(n^2) \end{align} ...
• 11
1 vote
46 views

### Master's Theorem recurrence

Given recurrence relation $T(n)=8T(n/6)+n \log n$, I get that the running time of the leaves should be $n^{\log_6 8}$ and $f(n)$ should be $n \log n$, but how can I know which one is bigger ?
54 views

### How to work out the odd case?

I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to ...
• 25
1 vote
51 views

### Is $n \log n$ in $O(n^{1.46-\varepsilon})$?

I am trying to figure out the solution of the recurrence relation $$T(n) = 5T(n/3) + n \log n$$ using the Master Method. I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the ...
• 25
96 views

1 vote
975 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)$, ...
• 23
58 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 ...
• 125
1 vote
803 views

• 147
1 vote
46 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 ...
• 147
1 vote
200 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$$
• 147
1k 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 ...
39 views

### Solving a recurrence in which $n$ decreases by $\sqrt{2n}$

I'm trying to solve the recurrence $T(n)= 2T(n-\log f(n))+ f(n)$, where $f(n) = 2^{\sqrt{2n}}$, using the master theorem. Which case applies here?
376 views

### Solution to T(n) = 2T(n/2) + log n

So my recursive equation is T(n) = 2T(n/2) + log n I used the master theorem and I find that a = 2, b =2 and d = 1. which is case 2. So the solution should be O(n^1 log n) which is O(n log n) I looked ...
250 views

### Solving T(n) = 3T(n/3)+sqrt(n) in terms of 𝜃 or O notions using master method [duplicate]

Please help me solve it in terms of Theta or Big O
• 11
2k views

### 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}$ ?
• 11
156 views

• 13
### Proof of inequality $\lceil x \rceil \le x+1$
I went through the Master Theorum extension for floors and ceiling section 4.6.2 in the book Introduction to Algorithms It had the following statement: Using the inequality $\lceil x \rceil \le x+1$ ...