People who code: we want your input. Take the Survey

# 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
2k views

### Recurrence problem T(n) = 2T(n − 1) + 1

Can I solve T(n) = 2T(n − 1) + 1 using the master theorem method? I don't think it cannot be solved with the master theorem because b=1. Please let me know, if my guess is wrong.
1answer
34 views

### How is this equation (involving a recurrence and $\phi(N)$) derived?

As in another question, let $$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\phi(N)) + \lg(\phi(N))^3 & \text{otherwise} \end{cases}$$ where $\phi(N)$ is Euler's totient function. Tasse ...
0answers
33 views

2answers
96 views

### How to use Master Theorem with strange format of $b$ parameter?

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as: $$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$ How can I apply the Master Theorem to ...
2answers
101 views

### Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
1answer
178 views

2answers
352 views

1answer
223 views

### Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?

I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence ...
0answers
32 views

### Trouble with Master Theorem concerning logarithm and square root [duplicate]

I have trouble understanding how to apply the master theorem in the following problem: $$T_2(1) = 1; T_2(n) = 4T_2(2^{\log \lfloor \frac{n}{2}\rfloor}) + \sqrt{n} \text{ for } n > 1.$$ My ...
2answers
93 views

1answer
623 views

### Regularity condition in the master Theorem in the presence of Landau notation for f

There already are many questions and answers about the importance of the regularity condition in case 3 of the Master Theorem. My question is about when can we safely assume the regularity condition ...
1answer
3k views

1answer
37 views

### Problem in analyzing asymptotic notation in using The Master Theorem [duplicate]

As we know for master theorem: T(n)=aT(n/b)+Θ(nd) this formate is required.. But for T(n)=2T(n/2)+2^n If I want to apply theorem what will be value of d here? We cant just take d=2 here..right?
1answer
1k views

### Intuition behind the Master Theorem

The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following: For a recurrence ...
2answers
6k views

### What is the recurrence form of Bubble-Sort

I understand how bubble sort works and why it is O(n^2) conceptually but I would like to do a proof of this for a paper using the master theorem. As an example: The recurrence form for merge sort is ...
1answer
3k views

### Does the master theorem apply to T(n) = 3T(n/3) + nlogn?

I am given an example of a case where the master theorem does not apply, but it seems like it should apply. This was the reasoning: $T(n) = 3T(n/3) + n \log n$ with $a = 3, b=3, f(n) = n\log n$ ...
1answer
178 views

### Trying to solve the recurrence relation by comparing 3 cases of master theorem

I am trying to understand how the master theorem is invoked on the following recurrence relation: $$T(n) = \sqrt{6006} T(n/2) + n^{\sqrt{6006}}.$$ So basically, I found the following source where ...
1answer
56 views

### Master Theorem linearithmic function

I am trying to find the running time of the given recurrence by the Master Theorem: $T(n)=16T(\frac{n}{2})+n^3\log^4 n$ I get $a=16$, $b=2$ and $f(n)=n^3\log^4n$, It seems that it's Case 1 of the ...
1answer
592 views

### Solving $T(n) = 4T(n/2) + n^2log_2(n)$ [duplicate]

My first thought was using the third case of the master theorem, but I am not sure if I can use $\epsilon \rightarrow 0$, so $f(n) \in \Omega(n^{log_2^4+\epsilon})$. Otherwise, I tried solving the ...
1answer
62 views