# Recurrence Relations

• Jun 13th 2013, 02:27 AM
mathmari
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)
• Jun 13th 2013, 04:26 AM
HallsofIvy
Re: Recurrence Relations
What does "Θ" mean?
• Jun 13th 2013, 04:41 AM
mathmari
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)$
• Jun 13th 2013, 05:27 AM
HallsofIvy
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,
• Jun 13th 2013, 10:51 AM
mathmari
Re: Recurrence Relations
And are the orders that I found right??