
Recurrence Relations
H! (Hi)
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)

Re: Recurrence Relations

Re: Recurrence Relations
f(n)=Θ(g(n)) $\displaystyle \Rightarrow \exists c_{1},c_{2},n_{0}>0: \forall n\geq n_{0}, c_{1}g(n)\leq f(n)\leq c_{2}g(n) $

Re: Recurrence Relations
Okay, that is the "order" relation. I would use just o(g(n)).
But if you are only saying, for example, that T(n) is "of the order of square root of n", you certainly have not SOLVED the equation,

Re: Recurrence Relations
And are the orders that I found right??