# Math Help - Recurrence Relations

1. ## Recurrence Relations

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)

2. ## Re: Recurrence Relations

What does "Θ" mean?

3. ## Re: Recurrence Relations

f(n)=Θ(g(n)) $\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)$

4. ## 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,

5. ## Re: Recurrence Relations

And are the orders that I found right??