Questions tagged [master-theorem]
Questions on the Master theorem, a method for obtaining asymptotic bounds on recurrences of a specific form.
199
questions
4
votes
2
answers
99
views
Proving that $T(n)=16T\left(\frac{n}{4}\right)+n! \in \Theta(n!)$
I am trying to prove that $T(n)\in\Theta(n!)$ for the following recurrence using the master theorem:
$\qquad T(n) = 16T\left(\frac{n}{4}\right)+ n!$
My attempt
We have that $f(n) = n! \in \Omega(n^{\...
- 143
1
vote
1
answer
31
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
50
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 ...
- 1
0
votes
1
answer
31
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(...
- 1
0
votes
1
answer
31
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 ...
- 31
1
vote
1
answer
109
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 ...
- 59
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^{\...
- 13
0
votes
1
answer
41
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 ...
- 13
3
votes
1
answer
442
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 ...
- 133
0
votes
1
answer
48
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
0
votes
1
answer
37
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^....
- 157
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 ...
1
vote
2
answers
199
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
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
103
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
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}...
- 109
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 ...
user154475
1
vote
1
answer
102
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)$ ...
- 113
0
votes
1
answer
67
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
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
0
votes
1
answer
114
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
620
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 ...
- 367
3
votes
2
answers
607
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 ...
- 367
-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
1
vote
0
answers
127
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
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)+\...
- 29
0
votes
2
answers
581
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
123
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
209
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 ...
- 21
0
votes
1
answer
618
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
155
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 ...
- 31
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 ...
- 138
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 ...
- 111
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 ...
- 1
0
votes
0
answers
430
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
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$$
- 21
1
vote
3
answers
1k
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
234
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
-1
votes
2
answers
127
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}$$
...
- 9
1
vote
1
answer
47
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
62
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
56
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
211
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)^{\...
- 133
2
votes
1
answer
278
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 $...
3
votes
1
answer
7k
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)$, ...
- 43
0
votes
1
answer
66
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 ...
- 235
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}^{...
1
vote
1
answer
180
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.
- 15
1
vote
1
answer
4k
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, ...