MathGroup Archive 1998

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

Search the Archive

Re: Problems with RSolve...

matt wrote:
> 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 can't seem
> to get
> Mathematica to give me an analytical solution.  Does anyone have any
> ideas as to why?
> thanks,
> matt
> housemat at

I do not think RSolve will handle this without a bit of massaging. Since
your progression is geometric rather than sequential you might mess
with a logarithmic substitution. Specifically, one might 

(i) Replace n by 2^k.

(ii) Replace t[2^j] by s[j].

(iii) Solve a recurrence for s.

(iv) Substitute back to get t[n].

In your particular example we begin with

In[1]:= eqn = t[2*n] == -1 + n + 2 t[n];

We rewrite this:

In[3]:= eqn2 =  eqn /. n->2^k;

In[4]:= eqn3 = eqn2 /. t[2^m_] -> s[m]
Out[4]= s[1 + k] == -1 + 2  + 2 s[k]

In[5]:= <<DiscreteMath`RSolve`

Say we have the first term in the sequence set to 1. We call RSolve with
eqn3 and this initial condition.

In[9]:=  soln = First[RSolve[{eqn3, s[0]==1}, s[k], k]]

                       -1 + k
Out[9]= {s[k] -> 1 + 2       k}

In[16]:= tsoln = Simplify[(soln /. s[j_]->t[2^j]) /. k->Log[2,n]]
                      n Log[n]
Out[16]= {t[n] -> 1 + --------}

You can infer from the gaps in the In[] sequence that this took a bit of

Daniel Lichtblau
Wolfram Research

  • Prev by Date: Leibniz for Windows beta now available
  • Next by Date: beep after calculation for Ver 3
  • Previous by thread: Re: Problems with RSolve...
  • Next by thread: output of 2d fortran arrays for post-processing (Q:)