Use mathematical induction to show that when n is an exact power of 2, the solu-...

Transcribed Image Text:

Use mathematical induction to show that when n is an exact power of 2, the solu- tion of the recurrence T(n) = 2 if n = 2, 2T (n/2) +n if n = 2k, for k > 1 is T(n) = n lgn. Hint: Use k as independent variable instead of n because n is an exact power of 2 and there is no case with n+ 1. First, verify the case for k = 1. Then, assume the formula is true for k and use the hypotheses to prove the formula is true for k+1. Finally, conclude the formula is true for k. Use mathematical induction to show that when n is an exact power of 2, the solu- tion of the recurrence T(n) = 2 if n = 2, 2T (n/2) +n if n = 2k, for k > 1 is T(n) = n lgn. Hint: Use k as independent variable instead of n because n is an exact power of 2 and there is no case with n+ 1. First, verify the case for k = 1. Then, assume the formula is true for k and use the hypotheses to prove the formula is true for k+1. Finally, conclude the formula is true for k.

Answer rating: 100% (QA)

Hence We can clearly se... View the full answer