Consider the recurrence relation T(n)= T(1) = 0(1) T([n/2])+T([n/2])+ bn, if n 2 1 Assuming that...

 

Transcribed Image Text:

Consider the recurrence relation T(n)= T(1) = 0(1) T([n/2])+T([n/2])+ bn, if n 2 1 Assuming that n is a power of 2, use a recursion tree to solve this recur- rence. Hint: The answer is not (n logn). (You might find the following useful: if r # 1, then r = (r+ 1)/(r 1).) 5. (20%) Use induction to prove that the upper bound you obtained in the previous exercise holds in the general case, when n is not necessarily a power of 2. (Do only the upper bound.) Consider the recurrence relation T(n)= T(1) = 0(1) T([n/2])+T([n/2])+ bn, if n 2 1 Assuming that n is a power of 2, use a recursion tree to solve this recur- rence. Hint: The answer is not (n logn). (You might find the following useful: if r # 1, then r = (r+ 1)/(r 1).) 5. (20%) Use induction to prove that the upper bound you obtained in the previous exercise holds in the general case, when n is not necessarily a power of 2. (Do only the upper bound.)