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

learn more… | top users | synonyms

-3
votes
0answers
18 views

Solve the following recursions using the Akra-Bazzi theorem [duplicate]

Can the following equations be solved using the Akra–Bazzi theorem and how? I don't quite understand the $h_i(x)$ part of the Akra–Bazzi theorem in Wikipedia. I'll appreciate an ...
3
votes
1answer
84 views

Master Method to solve recurrences is 'a' related to 'b'?

The master method allows us to solve certain recurrences of the form $$T(n) = aT(n/b)+f(n)\,,$$ where $a\ge1$ and $b>1$ are constants and $f(n)$ is a positive function with some further ...
-1
votes
1answer
50 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 ...
-1
votes
1answer
37 views

Is my analysis of this recurrence relation correct?

The following recurrence relation, $$T(n)=16T(\frac{n}{4}) + n^2$$ has been given to me to be solved via the Master Theorem. I'm pretty sure this is a case 2 situation, since $$\log_4{16} = 2$$ and ...
1
vote
2answers
59 views

$T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]

According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why? And which case of master theorem is it?
3
votes
4answers
57 views

Asymptotic Runtime of Interrelated Functions

I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me... How would I find the asymptotic ...
2
votes
2answers
122 views

Solution to recurrence $T(n) = T(n/2) + n^2$

I am getting confused with the solution to this recurrence - $T(n) = T(n/2) + n^2$ Recursion tree - ...
0
votes
1answer
82 views

Master theorem for $T(n) = 2T(n/2) + n^{2}\log n$

Would I use the third case of the Master Theorem for the recurrence equation $T(n) = 2T(n/2) + n^{2}\log n$? The condition given for the third case by Wikipedia is $f(n) = \Theta(n^c)$ when $c > ...
4
votes
0answers
55 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) + ...
6
votes
1answer
77 views

Why does Akra-Bazzi need that toll-function g is bounded?

Following up on vonbrand's answer I want to write a small document about stronger master theorems for our students, one of which is the Akra-Bazzi theorem. I have copied the theorem from their paper ...
4
votes
1answer
383 views

Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n

For analyzing the running time of an algorithm , I'm stuck with this recursive equation : $$ T(n) = \log(n) \cdot T(\log n) + n $$ Obviously this can't be handled with the use of the Master Theorem, ...
-1
votes
1answer
172 views

Solving a recurrence with the Master Theorem

Problem taken from here (page 3): http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-Handout.pdf $T(n) = 3T(\frac{n}{2}) + \frac{3}{4}n + 1$ $f(n) = \frac{3}{4}n + 1$ It says we cannot use ...
4
votes
1answer
317 views

Finding recurrence when Master Theorem fails

Following method is explained by my senior. I want to know whether I can use it in all cases or not. When I solve it manually, I come to same answer. $T(n)= 4T(n/2) + \frac{n^2}{\lg n}$ In above ...
2
votes
1answer
84 views

Not sure if my solution to following recurrence is correct

I have a recurrence relation, it is like the following: $T(e^n) = 2(T(e^{n-1})) + e^n$, where $e$ is the base of the natural logarithm. To solve this and find a $\Theta$ bound, I tried the ...
0
votes
0answers
25 views

The use of master theorem appriopriately [duplicate]

I have a recurrence relation and trying to use master theorem to solve it. The recurrence relation is: $T(n) = 3T(n/5) + n^{0.5}$ Can I use the master theorem in that relation? If so, can I say that ...
3
votes
2answers
145 views

Usage of master theorem for solving recursions

I know that master theorem is used for the recurrence relations of the form: T(n) = aT(n/b) + f(n) But in my question, i am supposed to solve the following recurrence relation by using master ...
11
votes
1answer
260 views

Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ...
3
votes
2answers
492 views

How to the examples for using the master theorem in Cormen work?

I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples $3T( \frac{n}{4} ) + n\log(n)$ $2T( \frac{n}{2} ) + ...
0
votes
1answer
131 views

Explanation of a specific recurrence with respect to Master Theorem

Concerning the Master Theorem. I have found the following equation as the base of analysis: $\quad T(n) = aT(n/b) + \Theta(n^k)$ but I also found the following: $\quad T(n) = aT(n/b) + ...
6
votes
3answers
1k views

Solving a recurrence relation with $\sqrt{n}$ as parameter

Let $T(n) = \sqrt{n} T(\sqrt{n}) + c\,n$ for $n \gt 2$ and some positive constant $c$ and $T(2) = 1$. I know the Master theorem, but I'm not sure as to how we could solve this relation using it. Any ...
0
votes
1answer
206 views

Big Omega of $n \log n$

While studying master method at recurrences topic I'm stacked at a point. It is written in the book as: $T(n) = 3T(n/4) + n \log n$, we have $a = 3, b = 4$, $f(n) = n \log n$, and ...
4
votes
2answers
237 views

Problems showing the constraint of master theorem case three holds

Prove or disprove the following statements: $T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \theta \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n ...
7
votes
2answers
2k views

Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
3
votes
1answer
658 views

Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence $$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$ by applying the Master Theorem. I am ...
5
votes
1answer
147 views

Finding lambda of Master Theorem

Suppose I have a recurrence like $T(n)=2T(n/4)+\log(n)$ with $a=2, b=4$ and $f(n)=\log(n)$. That should be case 1 of the Master theorem because $n^{1/2}>\log(n)$. There is also a lambda in case 1: ...
7
votes
2answers
1k views

Master theorem not applicable?

Given the following recursive equation $$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that $$ n^{\log_2(2)} = n.$$ Now we check the first two cases for ...
11
votes
3answers
566 views

Solving Recurrence Equations containing two Recursion Calls

I am trying to find a $\Theta$ bound for the following recurrence equation: $$ T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 $$ I figure Master Theorem is inappropriate due to differing amount of ...
4
votes
1answer
248 views

Master theorem and constants independent of $n$

I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version): $$T(n)=4T(n/2)+O(r)$$ $r$ is independent of $n$. Case 1 of the Master theorem applies ...
2
votes
1answer
582 views

Solve a recurrence using the master theorem

This is the recursive formula for which I'm trying to find an asymptotic closed form by the master theorem: $$T(n)=9T(n/27)+(n \cdot \lg(n))^{1/2}$$ I started with $a=9,b=27$ and $f(n)=(n\cdot \lg ...