- Thread starter
- #1

- Apr 14, 2013

- 4,047

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)

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)

Last edited by a moderator: