Welcome to our community

Be a part of something great, join today!

Recurrence Relations

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
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:

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
I agree with (a)–(d) using the version of the master theorem in this PDF document 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})$.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
And how could I solve the recurrence relation (e)?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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. This page 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)$.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Ok! Thanks!!!