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
903 views

### Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ...
20k views

### Solving a recurrence relation with √n as parameter

Consider the recurrence $\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$ for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$. I know the Master theorem for ...
17k views

### Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
8k views

### Solving Recurrence Equations containing two Recursion Calls

I am trying to find a $\Theta$ bound for the following recurrence equation: $$T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42$$ I figure Master Theorem is inappropriate due to differing amount of ...
18k views

19k views

### $T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]

According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why? And which case of master theorem is it?
636 views

8k views

### Solving recurrence relation with square root

I am trying to solve the following recurrence relation :- $T(n) = T(\sqrt{n}) + n$ using masters theorem. We can substitute $n = 2 ^ m$ $T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$ Now we can rewrite it ...
2k views

### What is the case 2 in master theorem?

I am confused about the statement of the Master theorem in CLRS book. Here is the link of the book CLRS. In page 94, the theorem, in case 2, states that: If $\displaystyle f(n)=\Theta(n^{\log_ba})$,...
2k views

### Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n

For analyzing the running time of an algorithm , I'm stuck with this recursive equation : $$T(n) = \log(n) \cdot T(\log n) + n$$ Obviously this can't be handled with the use of the Master Theorem, ...
I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true. My argument is as follows: Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\... 2answers 209 views ###$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$I'm trying to prove that for arbitrary$c > 0$,$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$Intuitively, this seems to be true to me (little-o implies ... 2answers 2k views ### How to the examples for using the master theorem in Cormen work? I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples$3T( \frac{n}{4} ) + n\log(n)2T( \frac{n}{2} ) + n\log(n)$... 1answer 2k views ### Meaning of polynomially larger or smaller in the context of the master method I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of$n^{\log_ba}$being polynomially smaller or ... 1answer 171 views ### Find the asymptotic bound$\Theta$of$t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$Find the asymptotic bound in terms of$\Theta$(Theta) using the master theorem for the following recursive equation. Assume that$t(n)= \Theta (1)$for suffucuently small$n$. $$t(n)=t(\frac{n}{... 1answer 350 views ### Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem? Wikipedia says that the following recurrence is inadmissible since there is a non-polynomial difference between f(n) = \frac{n}{\log n} and n^{\log_b a}:$$ T(n) = 2T\left(\frac{n}{2}\right) + \... 1answer 45 views ### Is there a difference between using$n$and$\Theta(n)$in recurrences? Is there a difference between$T(n)=2T(n/2)+n$and$T(n)=2T(n/2)+Θ(n)$when using the master theorem? I've seen it both ways and am a little confused. (Looking for the answer$nlogn$). 1answer 158 views ### 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, when$f(n)$is oscillating). Suppose, however, that$f(n)$is ... 1answer 159 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 149 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 734 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. 1answer 3k views ### Master theorem for$T(n)=T(n-1)+O(n)$The recurrence of selection sort is $$T(n) = T(n-1)+ O(n).$$ Can we apply the master theorem to this recurrence? I am confused because the master theorem can be applied to the following 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 ... 3answers 297 views ### Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n The questions is to find the running time T(n) of the following function:$$T(n)=3\cdot T(n/2) + n \tag{1}$$I know how to solve it using Master theorem for Divide and Conquer but I am trying to ... 1answer 321 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 ... 2answers 352 views ### Formulating the master theorem with Little-O- and Little-Omega notation In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this: Let a \geq 1 and b \gt 1 be constants, and let T : \mathbb{N} \rightarrow \... 1answer 59 views ### Could I apply the master theorem if my N/b is \varphi(N)? Let$$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$where \varphi(N) is Euler's totient function. Can I somehow express \... 2answers 97 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 ... 1answer 81 views ### Run time of a Simple Recurrence Given the recurrence T(n) = T(\sqrt{n}) + \theta(lglgn), provide an asymptotically tight bound on it's run time. My solution was to let m = 2\sqrt{n}, which leads to the recurrence S(m) = S(m/2) ... 2answers 89 views ### Master theorem: what to do with constant in parenthesis? 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 51 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)$$