Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [master-theorem]

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

1
vote
0answers
30 views

Trouble with Master Theorem concerning logarithm and square root [duplicate]

I have trouble understanding how to apply the master theorem in the following problem: $$T_2(1) = 1; T_2(n) = 4T_2(2^{\log \lfloor \frac{n}{2}\rfloor}) + \sqrt{n} \text{ for } n > 1.$$ My ...
2
votes
2answers
32 views

Possible to use Master theorem? $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$

The master theorem can be used in case of a recurrence relation of the form $T(n) = aT(\frac{n}{b}) + g(n)$ But is it possible to use the master theorem for recurrence relations of the form $T(n) = ...
0
votes
0answers
23 views

Solving Recurrence relation using Master Theorem

There is a recurrence relation like $T(n)=mT(n/2)+cn^2$ To solve this recurrence relation I am using Master Theorem. As per master theorem here a = m, b = 2, k=2 ,p=0 So $b^k= 2^2 = 4$ Now, ...
-1
votes
2answers
33 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 \\ &=...
1
vote
1answer
26 views

Master theorem recurrence relation

Consider I have the following recurrence $$T(n) = 10T(n/3) + \Theta(n^2\log^5 n)\,.$$ Now, by the master theorem, if we evaluate $n^{\log_{b}{a}}$, we get $n^{\log_{b}{a}} = n^{\log_{3}{10}} = n^{2....
0
votes
0answers
18 views

Big $O$-notation for Recurrence Relation [duplicate]

I have problem with recurrence relation in my homework. Here is the problem: Solve the recurrence $T(n) = T(\frac{n}{4}) + T(\frac{7n}{9})+n$ to get a big $O$ bound on the growth of $T(n)$, with ...
2
votes
2answers
76 views

Proving time complexity of $T(n) = 2T(n/3 + 1) + n$

I am working on proving the time complexity for the following problem, but believe I am stuck: $$T(n) = 2T(n/3 + 1) + n$$ I have checked out this link here on time complexity on cs.stackexchange ...
3
votes
1answer
31 views

Is there a difference between using $n$ and $\Theta(n)$ in recurrences?

Is there a difference between $T(n)=2T(n/2)+n$ and $T(n)=2T(n/2)+Θ(n)$ when using the master theorem? I've seen it both ways and am a little confused. (Looking for the answer $nlogn$).
1
vote
4answers
557 views

How to solve T(n)=2T(√n)+log n with the master theorem?

I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?
3
votes
1answer
55 views

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, when $f(n)$ is oscillating). Suppose, however, that $f(n)$ is ...
2
votes
0answers
24 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 ...
2
votes
1answer
60 views

Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$

Find the asymptotic bound in terms of $\Theta$ (Theta) using the master theorem for the following recursive equation. Assume that $t(n)= \Theta (1)$ for suffucuently small $n$. $$t(n)=t(\frac{n}{...
0
votes
0answers
26 views

How to implement a divide and conquest algorithm?

I'm taking a course on Algorithm design and I'm having a hard time with one of the practice problems given to us to work on. Below is the question, and then my attempted solution. You have ...
1
vote
2answers
80 views

What would be the time complexity for following recurrence?

T (n) = T (n/2) + 2^n I am solving this using master theorem and I calculated it to be big theta(log2 n) (log n to the base 2). But answer state it to be 2^n. Any help would be appreciated.
2
votes
1answer
471 views

Solving $T(n)=4T(n/4)+\log n$ using master theorem

$T(n)=4T(n/4)+\log n$ I'm solving this recurrence relation by master theorem. $a=4, b=4$ , $n^{\log_b a}=n^{\log_4 4}=n$ $f(n)=\log n=O(n^{1-\epsilon})$ when $\epsilon<1$, it is correct. So, $T(...
2
votes
1answer
152 views

Regularity condition in the master Theorem in the presence of Landau notation for f

There already are many questions and answers about the importance of the regularity condition in case 3 of the Master Theorem. My question is about when can we safely assume the regularity condition ...
1
vote
1answer
378 views

Master theorem for $T(n)=T(n-1)+O(n)$

The recurrence of selection sort is $$T(n) = T(n-1)+ O(n).$$ Can we apply the master theorem to this recurrence? I am confused because the master theorem can be applied to the following recurrence $$...
0
votes
0answers
59 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 ...
0
votes
1answer
74 views

Master theorem with $T(n) = 6T(n/10) + \lg^2 n$

So I think this falls under case 1...but I am not sure how to formally prove that $n^{lg_{10} 6}$ is asymptotically greater than $\lg^2 n$. I tried using L'hopitals but kinda reached a dead end. Here'...
1
vote
1answer
33 views

Solving Recurrence relation with master method?

I have to solve the following recurrence equation and I thought to solve it with case #3 of the master theorem. Can I do that? $$T(1) = c>0 $$ $$T(n) = 9T(n/3) + f(n)$$ $$f(n) = n^2\cdot lg^3 (n) +...
-1
votes
1answer
30 views

Problem in analyzing asymptotic notation in using The Master Theorem [duplicate]

As we know for master theorem: T(n)=aT(n/b)+Θ(nd) this formate is required.. But for T(n)=2T(n/2)+2^n If I want to apply theorem what will be value of d here? We cant just take d=2 here..right?
4
votes
1answer
236 views

Intuition behind the Master Theorem

The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following: For a recurrence ...
1
vote
2answers
2k views

What is the recurrence form of Bubble-Sort

I understand how bubble sort works and why it is O(n^2) conceptually but I would like to do a proof of this for a paper using the master theorem. As an example: The recurrence form for merge sort is ...
0
votes
0answers
497 views

Does the master theorem apply to $T(n) = 3T(n/3) + nlogn?

I am given an example of a case where the master theorem does not apply, but it seems like it should apply. This was the reasoning: $T(n) = 3T(n/3) + n log n$ with $ a = 3, b=3, f(n) = nlogn$ and ...
0
votes
1answer
65 views

Trying to solve the recurrence relation by comparing 3 cases of master theorem

I am trying to understand how the master theorem is invoked on the following recurrence relation: $$ T(n) = \sqrt{6006} T(n/2) + n^{\sqrt{6006}}. $$ So basically, I found the following source where ...
0
votes
1answer
38 views

Master Theorem linearithmic function

I am trying to find the running time of the given recurrence by the Master Theorem: $T(n)=16T(\frac{n}{2})+n^3\log^4 n$ I get $a=16$, $b=2$ and $f(n)=n^3\log^4n$, It seems that it's Case 1 of the ...
0
votes
1answer
259 views

Solving $T(n) = 4T(n/2) + n^2log_2(n)$ [duplicate]

My first thought was using the third case of the master theorem, but I am not sure if I can use $\epsilon \rightarrow 0$, so $f(n) \in \Omega(n^{log_2^4+\epsilon})$. Otherwise, I tried solving the ...
0
votes
1answer
45 views

Master Theorem Usage

I know how to use the master Theorem for a general formula e.g. $T(n) = a \cdot T(\frac{n}{b}) + f(n)$. I saw some books suggest that we can use the mastere theorem for formulas like: $T(n) = T(\frac{...
2
votes
1answer
188 views

Why is there no regularity condition in case 1 of the master theorem?

In case 3 of the master theorem, which is applicable when most of the work is being done at the top node (roughly speaking), we also need a regularity condition that the work done at the topmost level ...
0
votes
0answers
16 views

How to solve this recursive relation T(n)= 2T(n/2) + 3T(n/5) +n [duplicate]

I don't think I'm able to solve this using the master's theorem, and solving separately doesn't seem to make sense. How does one go about solving this recursive relation? T(n)= 2T(n/2) + 3T(n/5) +n
0
votes
1answer
990 views

Solving recurrence relation with square root

I am trying to solve the following recurrence relation :- $T(n) = T(\sqrt{n}) + n$ using masters theorem. We can substitute $n = 2 ^ m$ $T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$ Now we can rewrite it ...
2
votes
1answer
70 views

Run time of a Simple Recurrence

Given the recurrence $T(n) = T(\sqrt{n}) + \theta(lglgn)$, provide an asymptotically tight bound on it's run time. My solution was to let $m = 2\sqrt{n}$, which leads to the recurrence $S(m) = S(m/2) ...
0
votes
2answers
276 views

Applicabilty of master theorem (case 1) for T(n)=9T(n/3)+nlogn

I want to know if the recurrence equation $T(n) = 9T(\frac{n}{3}) + nlogn$, can or cannot be solved using master theorem. At first, I naively went for $O(n^2)$ applying case 1 of master theorem. But ...
1
vote
1answer
19 views

Finding any $\epsilon$ vs finding minimal $\epsilon$ for case 3 of Master theorem

I have a recurrence relation: $$T(n) = 3T(\frac{n}{4}) + n\lg n$$ and I want to prove that $T(n) = \Theta(f(n))$ using Master theorem. There's also an example in my textbook on this relation, they're ...
1
vote
1answer
168 views

Solving recurrence relations using substitution followed by tree method/masters theorem

$T(n) = 4T(\sqrt n) + n$ First I substitute n = $2^k$: $T(2^k) = 4T(2^{k/2}) + 2^k$ Now I rename the above as follows: $S(k)=4S(k/2) + 2^k$ Now if I try to use tree method on this in the ...
3
votes
3answers
471 views

Master Theorem: How to find the value of b in this recurrence relation

The master theorem is used with recurrences of the form T(n) = aT(n/b) + f(n) where a >=1 and b > 1, in which case the value of b can be easily seen from the ...
2
votes
3answers
4k views

Solving T(n) = 3T(n/3)+n/2 using master method

I thought I understood the Master Method quite well till I saw this question $T(n) = 3T(\frac{n}{3})+\frac{n}{2}$ My approach: $a = 3 ; b=3$ and $f(n) = \frac{n}{2}$ $n^{\log_b{a}}$ = $n^{log_3{...
0
votes
3answers
445 views

Meaning of the constants that appear in the Master Theorem

The general formula for time complexity is $T(n) = aT(n/c) + bn^k$. If $a> c^k$, the complexity is $O(n^{\log_c a})$. If $a = c^k$, it is $O(n^k \log n)$. If $a < c^k$, it is $O(n^k)$. $a$ is ...
5
votes
1answer
579 views

Applying the Master Theorem on Merge sort

I found the proof below in a textbook. I would like to know why it is important for the proof that it uses $\lceil \frac{n}{2} \rceil$ instead of just $\frac{n}{2}$? I know that you can't split into ...
0
votes
0answers
9 views

Need Help solving Recurrence Problem [duplicate]

I have this practice problem that I was given. I am trying to solve a specific recurrence equation T(n) = 4 when n <= 2 T(n) = 3T(n/3) + 5 when n > 2 ...
2
votes
1answer
171 views

Master Theorem and rounding up to the nearest integer

For the master theorem for recurrences of the form $$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)\,,$$ what difference would it make if the split was into calls of $\lceil n/b\rceil$ instead of $n/...
2
votes
3answers
284 views

Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n

The questions is to find the running time $T(n)$ of the following function: $$T(n)=3\cdot T(n/2) + n \tag{1}$$ I know how to solve it using Master theorem for Divide and Conquer but I am trying to ...
0
votes
4answers
721 views

Applying Master Theorem to: T(n) = T(n - 2) + n^2 [duplicate]

I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation: T(n) = T(n-2) ...
0
votes
0answers
13 views

Does master theorem apply differently for $n$ with restrictions? [duplicate]

Given $T(1) = 1$ and $T(n) = 4T(n/2) +n^2$ for $n\geq 2$, can I solve the recurrence for $T$ by applying the master theorem with $a = 4$, $b = d = 2$? This would give $T(n) = \Theta(n^2\log n)$.
1
vote
1answer
1k views

Solving using the master theorem [duplicate]

I am wondering why this $T(n)=3T(n/4)+n⋅lg(n)$ recurrence can be solve by Master Theorem case 3 but this $T(n)=2T(n/2)+n⋅lg(n)$ recurrence can not be solve by Master Theorem what is the difference ...
1
vote
1answer
41 views

Not convincing claim for Master Theorem Case 3

In a practice exam given in class, we were asked to solve the following recurrence $$T(n) = 2T(n/4) + \frac{n}{\log n}$$ The given solution claims that this falls in the third case of the Master ...
1
vote
1answer
392 views

Master Theorem Case 3 Regularity Condition

In case 3 of the master theorem, we have to show that $$ af(n/b) \leq cf(n). $$ I don't understand how I can setup this formula. As an example, we have $$ T(n)=3T(n/4) + n \lg n.$$ In this ...
1
vote
2answers
435 views

Using the Master theorem on a recurrence with non-constant a

I am trying to solve the following equation using master's theorem. $T(n) = 3^n T(\frac{n} 3) + O(1)$ Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what ...
-2
votes
1answer
51 views

Time complexity of a Divide and Conquer

I have Master theorem for finding complexities but the problem is Master theorem says For a recurrence of form $T(n) = aT(n/b) + f(n)$ where $a \geq 1$ and $b > 1$, there are following three cases:...
2
votes
1answer
64 views

Master method recurrence question [duplicate]

This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified $f(n)$ (as denoted below). For a recurrence of $$T(n) = a T(\frac{n}{b}) +...