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
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) $$\...
Frank's user avatar
  • 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 ...
Frank's user avatar
  • 147
1 vote
2 answers
292 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$$
Frank's user avatar
  • 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 ...
user128695's user avatar
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
-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 ...
KingAzaiez's user avatar
-1 votes
1 answer
510 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
Rako Maristella's user avatar
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}$ ?
Rako Maristella's user avatar
2 votes
2 answers
257 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? $$ ...
iich's user avatar
  • 23
1 vote
1 answer
921 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^...
snowneji's user avatar
  • 113
3 votes
1 answer
2k 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 ...
dairyknight86's user avatar
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 ...
Jon Anderson's user avatar
-3 votes
2 answers
599 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 ...
Roy Xu's user avatar
  • 111
1 vote
1 answer
75 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 ...
Veree's user avatar
  • 13
2 votes
1 answer
67 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$ ...
Sachin Bahukhandi's user avatar
3 votes
1 answer
573 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) ...
Abhishek Ghosh's user avatar
1 vote
0 answers
297 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
2 answers
80 views

Master Theorem applicable here?

Let $T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\ 1 & \text{if }n=1 \end{cases}$ I need to prove that $t(n) \in ...
Inocenciaa's user avatar
1 vote
1 answer
172 views

Proving van Emde Boas recurrence

I have tried to solve the following question: van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$. ...
GoldenRetriever's user avatar
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,...
user6530's user avatar
  • 954
2 votes
1 answer
87 views

Recurrence : $T(n) = 4T(n/2) + Θ(n^2/\log n)$

Is there a way to solve this recurrence using master theorem: $$T(n) = 4T(n/2) + Θ(n^2/\log n)$$
Benedict Dhm's user avatar
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
4 votes
1 answer
4k views

Conditions for applying Case 3 of Master theorem

In Introduction to Algorithms, Lemma 4.4 of the proof of the master theorem goes like this. $a\geq1$, $b>1$, $f$ is a nonnegative function defined on exact powers of b. The recurrence relation for $...
Jia Cheng Sun's user avatar
0 votes
0 answers
128 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
1 vote
0 answers
428 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 votes
1 answer
181 views

Solve recurrence with Master Theorem - Polynomially Smaller/Larger

The problem is to solve the recurrence using Master Theorem : $$T(n) = 2T(n/2)+\log_2 {n}$$ My attempt: $$ a=2, b=2, f(n)= \log_2 {n}, g(n)=n^{\log_b{a}}=n $$ I am torn between case 1 & the ...
34jbonz's user avatar
0 votes
1 answer
42 views

Solving a peculiar recurence relation

Given recurrence: $T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$ The way I solved is like this (using change of variables method, as mentioned in CLRS): Let $n = 2^k$ $T(...
Debasish Das's user avatar
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. ...
iamlearningmath's user avatar
2 votes
1 answer
91 views

Time complexity of algorithm inversely proportional to size of sub problem?

Let's say I have an algorithm with time complexity $T_n = T_\frac{n-1}2 + 1$, $T_0 = 0, T_1 = 1$. Assume (Induction hypothesis) $T_n = C\log_2(n+1)$ for some $C$. $T_1$ imposes $C \geq 1$. Therefore ...
Winter's user avatar
  • 125
3 votes
1 answer
486 views

Compare two complexity functions having the same asymptotic complexity

For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found: $A1: T_{A1}(n)=4n^2 +7log(n^2)$ $A2: T_{A2}(n) = 4T(n/2) + log(n)$ Say, technically ...
ddon-90's user avatar
  • 169
5 votes
1 answer
2k views

How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

Consider the recurrence $$T(n)= 4T(\sqrt n) + \log^2n. $$ I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
shashank jaiswal's user avatar
1 vote
1 answer
190 views

Why can we ignore the constant factor in Weis's proof of the Master Theorem

In the 4th edition of his Data Structures textbook, Weis gives a proof of part of the Master Theorem. This proof says "Let us ... ignore the constant factor in $\theta(N^k)$ ... I don't understand ...
Zack's user avatar
  • 121
1 vote
0 answers
273 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
2 votes
0 answers
508 views

Why can't we use the Master Theorem on recurrences with floor or ceiling operations? [duplicate]

From my understanding, using such operators on large numbers doesn't have an impact on running time, since the integer rounding becomes negligible after a certain point. For example, the recurrence $$...
hotelfloor's user avatar
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$...
hotelfloor's user avatar
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.
Sonya's user avatar
  • 97
0 votes
1 answer
41 views

How is this equation (involving a recurrence and $\phi(N)$) derived?

As in another question, let $$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\phi(N)) + \lg(\phi(N))^3 & \text{otherwise} \end{cases}$$ where $\phi(N)$ is Euler's totient function. Tasse ...
R. Chopin's user avatar
  • 237
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
139 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
1 vote
1 answer
99 views

Solving recurrence relation where the $f(n)$ has some constant factor $k$ where $0 < k < 1$

I am trying to see if a recurrence relation where $f(n)$ has some constant factor $k$, e.g. $f(n)=kn$ where $0 < k < 1$, is $O(n)$. I am reaching a different result depending which route I take. ...
garbagecollector's user avatar
0 votes
2 answers
72 views

What's an upper bound for this recurrence so I can take advantage of the Master Theorem?

Let $$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + 2T(\sqrt{N}) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$ where $\varphi(N)$ is Euler's totient function. My ...
R. Chopin's user avatar
  • 237
2 votes
1 answer
70 views

Could I apply the master theorem if my $N/b$ is $\varphi(N)$?

Let $$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$ where $\varphi(N)$ is Euler's totient function. Can I somehow express $\...
R. Chopin's user avatar
  • 237
2 votes
2 answers
131 views

How to use Master Theorem with strange format of $b$ parameter?

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as: $$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$ How can I apply the Master Theorem to ...
dalibor_j's user avatar
2 votes
2 answers
118 views

Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
jozko.vajda's user avatar
1 vote
1 answer
281 views

Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

I was trying to solve the following question while reviewing master theorem. Which of the following asymptotically grows faster. (a) $ T(n) = 4T(n/2) + 10n $ (b) $ T(n) = 8T(n/3) + 24n^2 $ (c) $ T(...
Debasis Jana's user avatar
0 votes
1 answer
58 views

Solving using the master theorem: T(n)=T(n/2)+nβ‹…log n and T(n)=T(n/8)+2.n [closed]

Could someone help me with these 2 questions? I do not understand the case 3 $T(n) = T(n/2) + n \log n$ $T(n)=T(n/8)+2 n$
Nepo's user avatar
  • 13
1 vote
1 answer
1k views

Proving recursion depth of merge sort

Hello I want to prove the recursion depth of merge sort, which is $O(\log(n))$. I think I can prove this by recurrence equation and the master theorem: $T(N)=2 T(n/2)+O(N) $ however i need to get $O(\...
raviolican's user avatar
3 votes
2 answers
542 views

Formulating the master theorem with Little-O- and Little-Omega notation

In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this: Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \...
Emily's user avatar
  • 133
0 votes
0 answers
225 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
5 votes
1 answer
5k views

Meaning of polynomially larger or smaller in the context of the master method

I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
Trixie the Cat's user avatar