       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)
T == 1
and you should have it.

RSolve[ {T[k] == 2 T[k-1] + (2^k - 1), T == 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

```

• Prev by Date: Limit, Series and O
• Next by Date: Re: Bubble help in palwttes
• Previous by thread: Problems with RSolve...
• Next by thread: Re: Problems with RSolve...