Skip to main content

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
1 vote
1 answer
28 views

Recurrence Upper Bound Estimation

I'm going through CLRS and was trying to solve for the asymptotic bound of the following recurrence (exercise 4-5.4) $$T(n) = 4T(n/2) + n^2\text{lg }n$$ According to CLRS definition of Master Theorem, ...
0 votes
1 answer
47 views

Does the Master Theorem apply to T(n) = 3T(n/3) + n/log2(n)?

Id say this is the first case of Master Theorem, but when I try to prove that the limit of f(n)/ n ^ (1-E) is 0, I cannot do it. Does anyone have a solution?
1 vote
1 answer
106 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 ...
0 votes
1 answer
46 views

Big O notation of T(n) = T(n/2) + O(log n) using master theorem?

I am aware that the algorithm has 1 recursive call of size n/2 and the non-recursive part takes O(log n) time. Master theorem formula is T(n) = aT(n/b) + O(n^d). In this case a = 1, b = 2, but I am ...
0 votes
1 answer
29 views

Solutions to Recurences

I am currently learning various techniques in order to solve recurrences. One of which is the generalized master's theorem. The current problem I am attempting is as follows $H(n) < 4H(2n/5) + H(...
0 votes
1 answer
30 views

$F(n, L) = 2F(n / 2, L) + nL + n^2 log(n)$ and Master Theorem

I have the following recurrence: $F(n, L) = 2F(n / 2, L) + nL + n^2 log(n)$. Am I correct in saying that $F(n, L) \in O(n \log(n) L + n^2 log(n))$? I got to this result by bounding the $nL$ and $n^2 \...
1 vote
0 answers
22 views

Is this a special case of a recurrence where the Master Method is not applicable?

So in an exam, this was the recurrence: $$ T(n) = 2T(n/2) + n log(n) -n + O(log(n))$$ $$T(1) = 1$$ Why does the master method not apply here? I think it is indeed int he form $$aT(n/b) + f(n)$$ You ...
1 vote
1 answer
106 views

Complexity of recursive function using Master theorem

this code aims to determine whether there exists a contiguous subarray starting from index 0 in the given array A whose elements sum up to the target value S. can we apply Master theorem to find out ...
1 vote
0 answers
31 views

Evaluating $T(n) = 4T(\frac{n}{5}) + \log n$: Master Theorem vs. Recursion Tree

I'm wondering where (how? why?) my reasoning (by imagining the recursion tree) deviates from the application of the Master Theorem (Case 1) to this recurrence. The Master Theorem gives $\Theta(n^{\...
0 votes
1 answer
38 views

What is the "big theta" order of the solution of T_n = T_(n/2) + log n, n > 0?

What method(s) could be used to solve this? I am still new to this stuff and would appreciate detailed justification for every step as well as some intuition and the examination of all possible viable ...
3 votes
1 answer
374 views

Time complexity of tree algorithm

I'm new to recurrence relations and master theorem so trying to learn. Say there's an algorithm $A$ whose input is the root of a binary tree $T$. $A$ recurses so that it's called on each and every ...
1 vote
3 answers
11k 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.
0 votes
1 answer
36 views

Can this reccurrence recurrence be solved using Master Theorem?

Assume we have: $$T(n)=7T(\frac{n}{2})+n^2\lg{n}$$ Can we solve it using master theorem? As we know $n^{\lg_2{7}}\approx n^{2.81}$. On the other hand, we have $f(n)=n^2\lg n$. So we should compare $n^....
1 vote
2 answers
187 views

Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction

We have this recurrence: $$T(n)=10T(\frac{n}{3})+n\sqrt{n}.$$ We can solve it using Master Theorem and say it is $\Theta(n^{\log_3{10}})$. I want to prove it using induction but I don't know the ...
0 votes
1 answer
38 views

find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$

We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and assume $T(1)$ is a constant. Find asymptotically tight bounds $\Theta(f(n))$ for $T(n)$. There's something that confuses me. We ...
0 votes
1 answer
66 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(...
0 votes
0 answers
32 views

Master Theorem - Solving Recurrence

I've been stuck for hours trying to solve the recurrence $T(n) = 7T(n/3) + n^2 + 2n$ by using case 3 of the master theorem. I've done a good chunk of the proof, but currently stuck attempting to solve ...
0 votes
0 answers
93 views

The master theorem soution to T(n) : T(n/4) + logn

When i tried to find the time complexity of this recurrence relation with the master theorem, I got log^2n, but I'm told that it's logn. I used the masters theorem, for this case.. a=b^k (1=4^0) ... ...
-1 votes
2 answers
124 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}$$ ...
11 votes
2 answers
21k views

Master theorem not applicable?

Given the following recursive equation $$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that $$ n^{\log_2(2)} = n.$$ Now we check the first two cases for $...
4 votes
2 answers
1k views

Does T(n) = 2 · T(2n) + n apply to Master method?

I'm trying to apply the master method to the following recurrence: $$T(n) = 2 \cdot T(2n)+n.$$ We have $a=2$ and $b=1/2$. Also, $f(n)=n$ and $n^{\log_b a} = n^{\log_{1/2} 2} = n^{-1}$ since $\log_{1/2}...
2 votes
2 answers
108 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$...
0 votes
0 answers
30 views

Solving a recurrence relation using the Master Theorem

I'm trying to solve this recurrence relation: $T(n) = T(\frac{n}{2}) + T(\frac{n}{5}) + T(\frac{n}{10}) + c_1n$ ; n > 1 $T(n) = c_2n$ ; n = 1 My first thought was to combine the fractions and ...
1 vote
1 answer
95 views

Why not $O(n^{\log_ba})$ for case 1 of the Master Theorem instead of $O(n^{(\log_ba) - \epsilon})$?

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)$ ...
-3 votes
1 answer
70 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
1 vote
1 answer
156 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
1 answer
113 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
572 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 ...
3 votes
2 answers
601 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 ...
2 votes
3 answers
207 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
2 answers
61 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 ...
0 votes
2 answers
257 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. ...
19 votes
3 answers
22k 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 ...
1 vote
2 answers
152 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)+\...
-3 votes
1 answer
67 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
121 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-...
2 votes
3 answers
200 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$$
1 vote
2 answers
117 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 ...
0 votes
2 answers
568 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
1 answer
154 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 ...
1 vote
1 answer
1k 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}^{...
0 votes
1 answer
592 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)$?
0 votes
1 answer
109 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
3 answers
981 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$
0 votes
2 answers
49 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 ...
0 votes
0 answers
413 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 ...
9 votes
2 answers
31k views

Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence $$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$ by applying the Master Theorem. I am ...
2 votes
1 answer
101 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,...
0 votes
2 answers
75 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) $$\...
0 votes
1 answer
3k 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}$ ?