What does "Θ" mean?
H!
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)