Questions tagged [master-theorem]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
36 views

Understanding Master Theorem

Someone who was explaining to me the master theorem said that for the case 1, we compare the $n^{log_b(a)}$ and $f(n)$. If the growth rate of $n^{log_b(a)}$ is greater than the growth rate of $f(n)$ ...
  • 101
0 votes
1 answer
29 views

In the Master Theorem, if one term is smaller than another, can we drop it from the equation and use big O instead of theta?

Considering the runtime analysis (with the master theorem) of the function below $T(n) = 12T(\frac{n}{4}) + 2\sqrt{n} + \log^4(n)$. As I could not figure out a way to get the equation in the form $T(...
  • 101
-3 votes
1 answer
36 views

How to solve T(n)=2T(√n)+(loglogn)^2?

Trying to solve the recurrence, but no clue how to deal with the (loglogn)^2 part
0 votes
1 answer
42 views

Solve Recurrence T(n) = 4T(n/4) + n*[log(n)]^2

I am trying to solve T(n) = 4*T(n/4) + n*[log(n)]^2 I decided to use Master Theorem so I found a,b=4 and logb(a)=1. I thought that 3rd case is the solution but I ...
0 votes
1 answer
72 views

Find matrix local minimum - two analysis which seem to get contradictory runtimes

Suppose you have an $n\times n$ matrix and you want to find a local minimum. To find it you scan the middle row and column and identify a minimum. If it is a local minimum, you're done; if not, you ...
  • 293
3 votes
2 answers
332 views

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Given the recurrence $$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$ My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
  • 337
-3 votes
1 answer
57 views

Solve the recurrence $3T(n) = T(n/3)+ \sqrt{\log n}$

How can you solve the recurrence $$3T(n) = T(n/3)+ \sqrt{\log n}$$ using the master theorem? I am lost in this question.
1 vote
0 answers
31 views

Big theta and big 0 bounds for iteration method and Master Theorem

In Algorithms 1, I'm noticing that big-Theta running times are always used for recurrence relations when using the iteration method. Meanwhile, using the Master Theorem always seems to result in a big-...
  • 111
0 votes
0 answers
31 views

Master theorem not applicable because "polynomially" slower

From what I understand the Master Theorem can't be applied when a function is slower or faster but not "polynomially greater or slower" what does polynomially faster or slower mean ?
1 vote
2 answers
102 views

Solve the recurrence equation $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$

I tried to solve the recurrence $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$ using the Master Theorem. I tried the following way: $n = 2^k$ $2^{\frac{2}{k}}\cdot T\left(2^k\right)+\...
0 votes
2 answers
141 views

How to solve $T(n) = 27T(n/9) + n^3$ with substitution method

I'm trying to bound this recurrence with the substitution method. My guess is $O(n^3)$. These are some steps: $$T(n) \leq cn^3 \\ T(n) \leq 27cn^3+n^3$$ How can I continue?
1 vote
2 answers
58 views

Regularity condition for cases 1 & 2

My question concerns the version of the Master Theorem described in CLRS and in this handout. I already understand the following: If the regularity condition in case 3 does not hold, then we can't ...
  • 11
2 votes
3 answers
83 views

Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?

The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
0 votes
1 answer
89 views

How to solve $T(n) = 2T(n/4) + n \log n$ with substitution method?

I am trying to solve this recurrence with substitution method. I guess $T(n) = \Theta(n \log n)$ (with Master Theoreme). Can someone show me how to demonstrate the upper bound $T(n) = O(n \log n)$?
1 vote
1 answer
52 views

Why doesn't master theorem solve $T(n) = 2T(n/2) + n\lg\lg n$?

Given two recurrences: $T(n) = 2 T(n/2) + n \lg \lg n$ $T(n) = 4 T(n/2) + n \lg \lg n$ I'd think that both works for master theorem, but the solution is that the first one cannot use masters ...
  • 21
0 votes
1 answer
49 views

How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
1 vote
1 answer
144 views

Master Method: Divide and Conquer

According to my evaluation ,the overall asymptotic running time of the below algorithm is O(n) ,since x (number of recursive ...
0 votes
2 answers
45 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 ...
  • 1
0 votes
0 answers
107 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 ...
  • 123
2 votes
3 answers
142 views

What is the asymptotic bound for $T(n)= 3T(\sqrt[3]{n})+n^3$?

What is the asymptotic bound? How do you get to the result? $$T(n)= 3 \cdot T(\sqrt[3]{n})+n^3$$
0 votes
3 answers
461 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$
1 vote
2 answers
137 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 ...
  • 13
0 votes
2 answers
75 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}$$ ...
1 vote
1 answer
46 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 ?
0 votes
2 answers
54 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 ...
  • 25
1 vote
3 answers
51 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 ...
  • 25
3 votes
1 answer
96 views

Justifying a claim in the proof 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)^{\...
2 votes
1 answer
61 views

Master theorem: $T(n)=10T(n/9)+n\lg(n)$

I am told to solve the recurrence $$T(n)=10T(n/9)+n\lg(n)$$ using the Master theorem. I then try to use case 3. However, I am unable to show that for $f(n)=n\lg(n)$ then $10f(n/9) \leq cn\lg(n)$ for $...
1 vote
1 answer
975 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)$, ...
  • 23
0 votes
1 answer
58 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 ...
  • 125
1 vote
1 answer
803 views

Solving the recurrence $T(n)=T(n-2)+n^2$ with the iterative method

I'm trying to solve this recurrence. I applied the iterative method: $$T(n) = T(n-2)+n^2$$ $$=T(n-4)+(n-2)^2+n^2$$ $$=T(n-6)+(n-4)^2+(n-2)^2+n^2$$ $$\cdot$$$$\cdot$$$$\cdot$$ $$=T(n-2k) + \sum_{i=0}^{...
1 vote
1 answer
98 views

How to prove $T(n) = 2T(n/2) + n/\log(n)$ can't be solved using the Master Theorem?

I have read (in this question) that this recursion can't be solved via Master Theorem. But I couldn't find exact and complete proof why the Master Theorem does not apply.
1 vote
1 answer
2k views

Solving $T(n) = 4T(n/2) + n^3$ with substituton method

I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, ...
2 votes
1 answer
80 views

Intuition on O(number of leaves) for master theorem

I am trying to develop the intuition of the master theorem for the case where $a > b^{d}$ [Case 3] in this video. In the video, they say that since most of the work is done at the leaves, we should ...
0 votes
2 answers
65 views

Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem

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 know that the solution is(with the help of the Master Theorem) $$\...
  • 147
1 vote
1 answer
46 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 ...
  • 147
1 vote
2 answers
200 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$$
  • 147
-2 votes
1 answer
1k 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 ...
0 votes
0 answers
39 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?
-1 votes
1 answer
376 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 ...
-1 votes
1 answer
250 views

Solving T(n) = 3T(n/3)+sqrt(n) in terms of 𝜃 or O notions using master method [duplicate]

Please help me solve it in terms of Theta or Big O
  • 11
0 votes
1 answer
2k 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}$ ?
  • 11
2 votes
2 answers
156 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? $$ ...
  • 23
1 vote
1 answer
668 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^...
  • 113
3 votes
1 answer
1k 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 ...
1 vote
1 answer
74 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 ...
-3 votes
2 answers
334 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 ...
  • 11
1 vote
1 answer
73 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 ...
  • 13
2 votes
1 answer
63 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$ ...
1 vote
1 answer
296 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) ...