# Questions tagged [master-theorem]

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

165 questions
Filter by
Sorted by
Tagged with
30 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 ...
37 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 ...
86 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$$
83 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$
80 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 ...
42 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} ...
45 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 ?
39 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 ...
46 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 ...
64 views

49 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)$, ...
53 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 ...
166 views

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 ...
92 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$$
405 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 ...
31 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?
41 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 ...
98 views

1k 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}$ ?
96 views

In analysis of algorithms, we sometimes use the (unsimplified) Master Theorem for recurrence relations. What should be done in the case that there is a constant factor in the numerator following T? $$... 1answer 502 views ### Solve Recurrence for T(n) = 7T(n/7) + n I'm trying to solve the recurrence for T(n) = 7T(n/7) + n. I know using Master Theorem it's O(n\log_7n), but I want to solve it by substitution method. At level i, I get: 7^i T(n/7^i) + (n+7n+7^... 1answer 402 views ### Applying Case 3 of Master Theorem to T(n) = 9T(n/3) + n^3 Given T(n) = 9T(n/3) + n^3, I know that a =9, b=3, and f(n) = n^3 and n^{\log_{3}9} = n^2 thus Case 3 applies: n^{\log_{b}a} < f(n), n^2 < n^3. Can someone explain how to apply the ... 1answer 43 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 192 views ### solving recurrence T(n) = T(√n) + theta((lg lg n)) My solution: let m = lg n. Then n = 2^m. T(2^m) = T(2^(m/2)) + theta(lgm). Let S(m) = T(2^m). Then S(m) = S(m/2) + theta(lgm). Applying master theorem, I get m^(lg1) = 1 which is asymptotically ... 1answer 70 views ### Does 20n belong to O(n^{1-\epsilon}) for some \epsilon > 0? I am quite new to master theorem and I would like to ask the following question for$$𝑇(𝑛)=4𝑇(𝑛/4)+20𝑛.$$If there is a constant value like 20n does it affect the equation? Would the equation ... 1answer 56 views ### 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 ... 1answer 117 views ### Clarification of the proof involving the regularity condition in Master Theorem I was going the text Introduction to Algorithms by Cormen et al. Where I came across the following statement in the proof of the third case of the Master's Theorem. (The Statement of Master theorem) ... 0answers 138 views ### Advanced Master Theorem? I have learned the Master's Theorem from the CLRS textbook (2nd Edition), the form of the Master Theorem given in the above text is associated with the proof of each and every case. So at the end I ... 2answers 58 views ### Master Theorem applicable here? Let T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\ 1 & \text{if }n=1 \end{cases} I need to prove that t(n) \in ... 1answer 61 views ### Proving van Emde Boas recurrence I have tried to solve the following question: van Emde Boas Bounds Show that T(u) = T(\sqrt{u}) + O(1) has the solution T(u) = O(\log\log u). Hint: consider the binary representation of u. ... 1answer 65 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 58 views ### Recurrence : T(n) = 4T(n/2) + Θ(n^2/\log n) Is there a way to solve this recurrence using master theorem:$$T(n) = 4T(n/2) + Θ(n^2/\log n)$$0answers 32 views ### Possible to use master method on T(n)/g(n)=aT(n/b)+f(n) The master theorem can be used in case of a recurrence relation of the form 1) T(n) = aT(\frac{n}{b}) + f(n) My question is whether it can be applied if 2) \frac{T(n)}{g(n)} = aT(\frac{n}{b}) + ... 1answer 375 views ### Conditions for applying Case 3 of Master theorem In Introduction to Algorithms, Lemma 4.4 of the proof of the master theorem goes like this. a\geq1, b>1, f is a nonnegative function defined on exact powers of b. The recurrence relation for ... 0answers 35 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, ... 0answers 117 views ### How to use master theorem to solve T(n)=4T(n/8) + \sqrt n (\log_2 n)^2 I want to solve the following using master theorem. T(n)=4T(n/8) + \sqrt n (\log_2 n)^2 I have: a=4, b=8,f(n)=\sqrt n (\log_2 n)^2 I calculate n^{log_b a} = n^{\log_8 4} = n^{2/3} I ... 1answer 97 views ### Solve recurrence with Master Theorem - Polynomially Smaller/Larger The problem is to solve the recurrence using Master Theorem :$$T(n) = 2T(n/2)+\log_2 {n}$$My attempt:$$ a=2, b=2, f(n)= \log_2 {n}, g(n)=n^{\log_b{a}}=n $$I am torn between case 1 & the ... 1answer 39 views ### Solving a peculiar recurence relation Given recurrence: T(n) = T(n^{\frac{1}{a}}) + 1 where a,b = \omega(1) and T(b) = 1 The way I solved is like this (using change of variables method, as mentioned in CLRS): Let n = 2^k T(... 2answers 148 views ### Proving complexity of T(n)=2T(n/3 + 1) + n non-Akra-Bazzi We know that the complexity of T(n)=2T(n/3 + 1) + n is \Theta(n), as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work. ... 1answer 70 views ### Time complexity of algorithm inversely proportional to size of sub problem? Let's say I have an algorithm with time complexity T_n = T_\frac{n-1}2 + 1, T_0 = 0, T_1 = 1. Assume (Induction hypothesis) T_n = C\log_2(n+1) for some C. T_1 imposes C \geq 1. Therefore ... 1answer 175 views ### Compare two complexity functions having the same asymptotic complexity For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found: A1: T_{A1}(n)=4n^2 +7log(n^2) A2: T_{A2}(n) = 4T(n/2) + log(n) Say, technically ... 1answer 823 views ### How to solve T(n)= 4T(\sqrt n) +\log^2n? Consider the recurrence$$T(n)= 4T(\sqrt n) + \log^2n.  I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
In the 4th edition of his Data Structures textbook, Weis gives a proof of part of the Master Theorem. This proof says "Let us ... ignore the constant factor in $\theta(N^k)$ ... I don't understand ...
I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$. \$V(j, k) = \begin{cases} tj & k \leq 2 \\...