Complexity of Recursive Functions:
from a program we can calucale it's complexity by counting the sum of the contributions, but for recursive functions it's a bit more complex, because we need to account for the cost of the recursive call itself.
Major Families of Techniques for resolving Recurrence:
-
Iterative Method:
The equation is expanded step by step until a closed-form expression (a function of n and constants) is determined.
-
Substitution Method:
An estimated bound (e.g., O(n²)) is assumed, then mathematical induction is used to verify the guess. -
Recursion Tree Method:
A recursion tree is constructed, where the nodes represent the costs at various levels of recursion.
We saw an example of this tree in the Fibonacci case.- It can help in formulating a good "guess" for the substitution method.
-
Master Theorem Method:
Based on the Master Theorem, useful for divide-and-conquer algorithms of the form T(n) = aT(n/b) + f(n).