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