MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Problems with RSolve...


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


  • 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...