Solving Recurrence Relations: Are My Results Right?

[mathmari]

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)

 

[Evgeny.Makarov]

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})$.

 

[mathmari]

And how could I solve the recurrence relation (e)?

 

[Evgeny.Makarov]

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)$.

 

[mathmari]

Ok! Thanks!