Help with Recurrences?

[JonTheBaller]

Can someone explain recurrences to me? I'm referring to recurrences when dealing with recursive algorithms, where the equation is in the form T(n).

Any help would be appreciated, because I am really really confused as to how you solve recurrences.

 

[stonecold3169]

recurrences can be tricky, and a lot of the time require more mathmatical knowledge then CS. Once you find a basis for your arguement, it's easy enough to solve. Thats the tricky part though.

It helps to have access to the running time of common mathmatical operations which can come up a lot (such as, sum of the first n integers = n(n+1)/2 runs in time theta log(n))

Recurrence relationships typically follow one of two patterns. Either they go up by a constant factor, as in a geometric sequence, or they follow a system where, say, part of T(n) cancels out with part of T(n-1) so that it's actually a very simple problem. It's just hard reaching that point.

Hopefully this gives you the basic idea, if you have more questions, or a more specific question feel free to post or PM me, and I'll get back to you

 

[ArmenK]

Use substitution method, recurrence tree, or master theorem. Master theorem is best if you can apply it.
Heres a pdf that google turned up: Text