Information about the complexity of recursive algorithms

Question

hi guys

does anyone know about some good sources about counting complexity of recursive algorithms? somehow recurrent equation isn't really popular title for web page or what, I just couldn't google out anything reasonable...

Answer 1

I think you would have had more luck with recurrence equation.

Answer 2

This is a complex topic that is not so well-documented on free licterature on internet.

I just did a similar exam and I can point you to the handbook written by my teacher: PDF Handbook

This handbook covers mostly another tool called generating functions that are useful to solve any kind of recurrence without bothering too much on the kind of recurrence.

There is a good book about Analysis of Algorithms that is An introduction to the Analysis of Algorithms (amazon link) by Sedgewick and Philippe Flajolet but you won't find it online (I had to scan parts of it).

By the way I've searched over internet a lot but I haven't found any complete reference with examples useful to learn the techniques.

Answer 3

You can also check out the Master theorem.

In the analysis of algorithms, the master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice. It was popularized by the canonical algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, which introduces and proves it in sections 4.3 and 4.4, respectively. Nevertheless, not all recurrence relations can be solved with the use of the master theorem.