Re: Question about using telescoping with recurrence in studying algorithms.



smurrish wrote:

I am relatively new to the study of algorithms, do not have an
extensive background in mathematics, and find some of the steps
in solving an equation to represent how long an algorithm will
take to be perplexing.

The use of telescoping in order to come up with a solution is
not intuitive to me. Could someone please point to a website or
book that will very explicitly go through each step and explain
this process in detail? Often in Sedgewick's Algorithms in C++
book when it says with x, y, z it is clear that a, b,c... it is
not clear to me.

I think you are referring to repeatedly substituting the right-hand
side of a recurrence relation into itself in order to guess the form
of its solution -- what Alf dug up is about something else entirely.
I can't point you anywhere in particular, but you might start by
looking over the hits on
http://www.google.com/search?q=solve+recurrence+repeated+substitution
for something with the level of detail you seek.


Martin

--
Quidquid latine scriptum sit, altum viditur.
.