Recurrence Tree

[subaha]

Solve the following recurrence using a tree method

 

1. T(n) = T(n/2) + c

2. 3(Tn/2) + cn^2

[khaled]

I'm not sure, I'm not good at this

 

Problem # 1

 

 

 

Assume: [math]T(X) = 0 \; FOR \; X < 1 \; AND \; X = 1[/math]

 

[math]T(n) = T(n/2) + c[/math]

 

[math]T(n) = ( T(n/4) + c ) + c[/math]

 

[math]T(n) = (( T(n/8) + c ) + c ) + c[/math]

 

...

 

[math]T(n) = T(n/n) + c + c + .. + c = T(1) + log_{2}{n} \; c = \; FLOOR(log_{2}{n}) c[/math]

 

 

 

Edited May 2, 2012 by khaled