Questions tagged [master-theorem]

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

31 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6 votes
0 answers
219 views

Are there master theorems that deal with parameters of the form $n-c$?

While thinking about this question on a recurrence I checked out some stronger master theorems. Unfortunately, they do not seem to apply because terms $\qquad\displaystyle T(n) = \dots + T(n-1) + \...
Raphael's user avatar
  • 72.4k
2 votes
0 answers
35 views

Possible to use master method on T(n)/g(n)=aT(n/b)+f(n)

The master theorem can be used in case of a recurrence relation of the form 1) $T(n) = aT(\frac{n}{b}) + f(n)$ My question is whether it can be applied if 2) $\frac{T(n)}{g(n)} = aT(\frac{n}{b}) + ...
David's user avatar
  • 21
2 votes
0 answers
88 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 ...
user2316602's user avatar
1 vote
0 answers
20 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 ...
Yuirike's user avatar
  • 31
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^{\...
Per48edjes's user avatar
1 vote
0 answers
114 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-...
There's user avatar
  • 111
1 vote
1 answer
100 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 ...
Jon Anderson's user avatar
1 vote
0 answers
289 views

Advanced Master Theorem?

I have learned the Master's Theorem from the CLRS textbook (2nd Edition), the form of the Master Theorem given in the above text is associated with the proof of each and every case. So at the end I ...
Abhishek Ghosh's user avatar
1 vote
0 answers
416 views

How to use master theorem to solve $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$

I want to solve the following using master theorem. $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$ I have: $a=4, b=8,f(n)=\sqrt n (\log_2 n)^2$ I calculate $n^{log_b a} = n^{\log_8 4} = n^{2/3}$ I ...
Mandy's user avatar
  • 177
1 vote
0 answers
272 views

How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?

I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$. $V(j, k) = \begin{cases} tj & k \leq 2 \\...
user12055579's user avatar
0 votes
1 answer
23 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(...
kusakus's user avatar
0 votes
1 answer
37 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?
Mara F's user avatar
  • 1
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 ...
Jeremy Bowens's user avatar
0 votes
0 answers
64 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) ... ...
Yor's user avatar
  • 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 ...
user avatar
0 votes
0 answers
397 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 ...
super.t's user avatar
  • 123
0 votes
0 answers
43 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?
Jonardan Cena's user avatar
0 votes
0 answers
120 views

Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...
Mandy's user avatar
  • 177
0 votes
0 answers
36 views

Does the master theorem applies to this recurrence?

The recurrence: $T(n) = pT(n/q) + \log n$ for p < q and p >= 2. So, I've figured out it would fall into case 1, since we have $n^{log_{q}p} = n^r $, for $0<r<1$, which would mean that $f(...
user109641's user avatar
0 votes
0 answers
137 views

How to find running time complexity of divide and conquer method without Master Theorem

I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree ...
user avatar
0 votes
0 answers
220 views

Master Theorem Help - How to make the value of "b" greater than 1 as required by the Master Theorem? What math is involved?

I know how to identify the parts of the Master Theorem, and I know that it is a recurrence relation. I don't understand how to make the "b" value greater than 1. Please see the image. I know the math ...
John Doe X's user avatar
0 votes
0 answers
211 views

Finding runtime of a recurrence relation with a fractional power

Consider the following algorithm and find the tightest Big-$O$: Assume $\texttt{multiplyKS}$($A,B$) is $O(n^{1.58})$ and $\texttt{Add}($A,B$)$ is $O(n)$. If my runtime is $T(n)$, I have: Lines 1 ...
darylnak's user avatar
  • 275
0 votes
0 answers
31 views

The applicability of the Master Theorem and calculation of asymptotic limits

Given the following recursive equation $T(n)=3T(\dfrac{n}{8})+ Θ(n^{1/3})$ I want to know how to explain the applicability of the Master theorem in a rigorous way and what means asymtotic limits of ...
ssrvz's user avatar
  • 1
0 votes
0 answers
702 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 ...
Vagabond's user avatar
0 votes
1 answer
28 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 \...
Jovan Komatovic's user avatar
-1 votes
2 answers
129 views

Using Iterative method to find recurrence relation vs Master Theorm

I'm trying to solve this recurrence relation using the iterative method and i keep getting the different answer from using the master theorem. $$\begin{aligned} T(n) &= 5T(n/2) +n^2 \\ &=...
RecurrenceDifference's user avatar
-1 votes
1 answer
340 views

A difficult master theorem problem

Consider the function $B:\mathbb{N}\rightarrow\mathbb{R}$ defined by $$ B(n) = \begin{cases} 1 &\text{if $n\le 2$}\\ B\left(\left\lceil\frac{n}{\log_2n}\right\rceil \right)+n&...
John's user avatar
  • 11
-1 votes
2 answers
123 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}$$ ...
Zero One's user avatar
-1 votes
1 answer
197 views

Master Theorem Questions?

NOTE: I asked this on mathstackexchange, but didn't get the responses I wanted, thought I should post in CS. Sorry if i did something wrong but i am a newbie. State the asymptotic (worstcase) ...
duvalgup22's user avatar
-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
Chris W's user avatar
-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.
tjbeast's user avatar