Questions tagged [master-theorem]
Questions on the Master theorem, a method for obtaining asymptotic bounds on recurrences of a specific form.
188
questions
1
vote
1
answer
31
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^....
- 55
0
votes
1
answer
34
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 ...
- 151
1
vote
2
answers
146
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 ...
- 151
0
votes
0
answers
31
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
42
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}...
- 99
0
votes
0
answers
29
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
81
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
58
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
66
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
103
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
416
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 ...
- 315
3
votes
2
answers
557
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
65
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
92
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
144
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
493
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
96
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
186
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
355
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
112
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
94
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
154
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
48
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
344
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
193
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
828
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
190
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
117
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
56
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
54
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
181
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
196
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 $...
2
votes
1
answer
5k
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)$, ...
- 33
0
votes
1
answer
63
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 ...
- 225
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
156
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
3k
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
138
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 ...
- 659
0
votes
2
answers
74
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
49
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
272
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
2k
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
42
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?
- 111
-1
votes
1
answer
1k
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
462
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
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}$ ?
2
votes
2
answers
237
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
863
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