Re: Problems with RSolve...
- To: mathgroup at smc.vnet.net
- Subject: [mg14575] Re: Problems with RSolve...
- From: sguyer at NOSPAMPLEASEcs.vt.edu (Scott A. Guyer)
- Date: Fri, 30 Oct 1998 03:07:43 -0500
- Organization: Virginia Tech
- References: <719fiq$ldb@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
In article <719fiq$ldb at smc.vnet.net>, housemat at wam.umd.edu says...
> I'm having problems with RSolve when applying it to the following type
> of recurrence
> relation:
>
> T(n) = 2 T(n/2) +n -1
>
> (The type of relation you get when analyzing Merge-Sort).
I think all you need is a change the recurrence variable by assuming
that n = 2^k and taking the binary log of n. The following recurrence
is, therefore, equivalent.
T[k] == 2 T[k-1] + (2^k - 1)
Add a base case,
T[1] == 1
and you should have it.
RSolve[ {T[k] == 2 T[k-1] + (2^k - 1), T[1] == 1}, T[k], k ]
Gives the result,
{{T[k] --> 1 - 2^k + 2^k k}}
Going back to the variable substitution, n = 2^k, we get
T[n] = n Log[2,n] + (n - 1)
Cheers,
--
Scott A. Guyer
Virginia Tech