# Questions tagged [master-theorem]

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

144 questions
Filter by
Sorted by
Tagged with
19 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?
24 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 ...
25 views

50 views

### Solving T(n) = 3T(n/3)+sqrt(n) using master method

I want to know how to find the complexity of this recurrence.
61 views

55 views

### Can we apply the Master Theorem to the following recurrence?

Our recurrence is $$T(n)= \begin{cases} T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if n>1} \\ 1 & \text{if n=1.} \end{cases}$$ I have identified $a = 1 > 0$, and $b = 2 > 1$...
449 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.
30 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 ...
33 views

77 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 ...
96 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 ...