Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: HARD: Help with math problems involving algorithms
Posted:
Feb 18, 1999 9:55 PM


ninthward9@hotmail.com writes:
> 3) Use mathematical induction to show that the solution of the recurrence > > T(n) = {2 if n = 2 > {2(n/2) + n if n = 2^k, k>1 > > is T(n) = n lg n (where I belive lg n is base 2) for all values of n > that are exact powers of 2.
Exact powers of 2 have the form 2^k for some nonnegative integer k. So it suffices to show T(2^k) = (2^k) * lg (2^k) for all nonnegative integers k. Now you can apply induction on k.
 [If you post a response, no need to cc me; if you cc me, please say so.] Infernal competition granted unto them, Lord, and natural selection select among them. Eternal rest granted unto the unfit, Lord, and perpetual light shined upon them.



