Information on the complexity of recursive algorithms

Question

Does anyone know of good sources about calculating the complexity of recursive algorithms? anyway, the recurrence equation is not a very popular name for a web page or what, I just could not google out anything reasonable ...

Answer 1

This is a complex topic that is not well documented for free licensing on the Internet.

I just did a similar exam, and I can point you to a reference written by my teacher: a PDF reference

This handbook focuses mainly on another tool, called generating functions, which are useful for solving any kind of repetition without worrying too much about repetition.

There is a good book on Algorithm Analysis , which is an introduction to algorithm analysis ( amazon link ) from Sedgewick and Philippe Flajolet, but you won't find it on the Internet (I had to scan parts of it).

By the way, I searched many times over the Internet, but I did not find full help with examples useful for learning techniques.

Answer 2

I think you would be more fortunate with the repetition equation .

Answer 3

You can also check the Master Theorem .

When analyzing the algorithms, the master theorem, which is a specific case of the Acra-Bazzi theorem, provides a cookbook solution in asymptotic terms to repeat the relationship of types that occur in practice. He was popularized a textbook on canonical algorithms An introduction to the algorithms of Cormen, Leiserson, Rivest and Stein, which introduces and proves this in sections 4.3 and 4.4, respectively. However, not all repetition relationships can be solved using the main theorem.