Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: HARD: Help with math problems involving algorithms
Replies: 2   Last Post: Feb 18, 1999 9:55 PM

 Messages: [ Previous | Next ]
 Albert Y.C. Lai Posts: 28 Registered: 12/6/04
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 non-negative integer k.
So it suffices to show T(2^k) = (2^k) * lg (2^k) for all non-negative
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.

Date Subject Author
2/15/99 ninthward9@hotmail.com
2/15/99 Brian Evans
2/18/99 Albert Y.C. Lai