MHB Solving Recurrence Relations: Are My Results Right?

AI Thread Summary
The discussion revolves around solving various recurrence relations using the master theorem. The user presents five relations and their corresponding solutions, agreeing with the results for the first four but questioning the application of the theorem to the fifth. They note that the master theorem does not apply to the fifth relation since the function does not meet the necessary conditions. The user suggests that an upper bound version of the master theorem could be used to derive a solution for the fifth relation, proposing that it could yield T(n) = O(n^2 log n). The conversation concludes with uncertainty about the exact bounds for the fifth relation, depending on the behavior of the last term.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Helloo!
I have to solve the following recurrence relations:
(a) T(n)=sqrt(2)*T(n/2)+lgn
(b) T(n)=3*T(n/4)+nlgn
(c) T(n) 3*T(n/3)+n/2
(d) T(n)=5*T(n/2)+Θ(n)
(e) T(n)=9*T(n/3)+O(n^2)
Could you tell me if my results are right?
Using the master theorem I found:
(a)T(n)=Θ(sqrt(n))
(b)T(n)=Θ(nlgn)
(c)T(n)=Θ(nlgn)
(d)T(n)=Θ(n^(log(2)5)
(e)T(n)=Θ(n^2*lgn)
 
Last edited by a moderator:
Physics news on Phys.org
I agree with (a)–(d) using the version of the master theorem in http://www.csail.mit.edu/~thies/6.046-web/master.pdf from MIT, but not in Wikipedia. (The former document is given as a footnote in the Wiki article.) The reason is that Wikipedia uses only Θ and not O or Ω.

However, the theorem does not seem to apply to (e) because $f(n)=O(n^{\log_ba})$. Your answer would be correct by case 2 of the theorem if $f(n)=\Theta(n^{\log_ba})$.
 
And how could I solve the recurrence relation (e)?
 
mathmari said:
And how could I solve the recurrence relation (e)?
I am pretty sure there is an upper bound version of the master theorem, which says, in particular:

If $T(n) = aT(n/b) + f(n)$ where $f(n) = O(n^{\log_ba})$, then $T(n)=O(n^{\log_ba}\log n)$,

but I am having trouble finding exactly this formulation. http://www.eecis.udel.edu/~saunders/courses/621/11s/notes/notes/Master-theorem.html seems to say something pretty close. It also should be easy to change the proof from Θ to O.

If this is correct, then $T(n) = O(n^2\log n)$ in (e). I am not sure one can say more because if the last term is, in fact, $n^2$, then $T(n)=\Theta(n^2\log n)$, but if it is 0, then $T(n)=\Theta(n^2)$.
 
Ok! Thanks!
 

Similar threads

Replies
2
Views
1K
Replies
18
Views
3K
Replies
2
Views
2K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
5
Views
2K
Replies
1
Views
1K
Back
Top