# Questions tagged [master-theorem]

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

117 questions
Filter by
Sorted by
Tagged with
14 views

### Why can we ignore the constant factor in Weis's proof of the Master Theorem

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 ...
43 views

402 views

### Proving time complexity of $T(n) = 2T(n/3 + 1) + n$

I am working on proving the time complexity for the following problem, but believe I am stuck: $$T(n) = 2T(n/3 + 1) + n$$ I have checked out this link here on time complexity on cs.stackexchange ...
43 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$).
5k views

### How to solve T(n)=2T(√n)+log n with the master theorem?

I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?
108 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 ...
29 views

### Reference request: Leaf-heavy master theorem algorithms

I know many algorithms that can be analyzed using master theorem, but the only algorithm I know where the time is dominated by the leaves is fast matrix multiplication. Are there other recursive ...
126 views

253 views

### How to find lower bound of f(n) for master theorem

I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has. I usually ...
80 views

### Master theorem with $T(n) = 6T(n/10) + \lg^2 n$

So I think this falls under case 1...but I am not sure how to formally prove that $n^{lg_{10} 6}$ is asymptotically greater than $\lg^2 n$. I tried using L'hopitals but kinda reached a dead end. Here'...
38 views

I have to solve the following recurrence equation and I thought to solve it with case #3 of the master theorem. Can I do that? $$T(1) = c>0$$ $$T(n) = 9T(n/3) + f(n)$$ $$f(n) = n^2\cdot lg^3 (n) +... 1answer 35 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 544 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 4k 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 ... 0answers 852 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) = nlogn and ... 1answer 111 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 ...
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 ...
### 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 ...