The time complexity of recursive functions is a little different than iterative functions. The time complexity of a recursive function is determined by the "Master Theorem".
## The Master Theorem
Given a recursive relation every function of the following type:
T(n) = a*T(n/b) + f(n)We can determine the time complexity by comparing f(n) with nlogb(a):
- If f(n) is O(nc), where c < logb(a), then the time complexity is Θ(nlogb(a)).
- If f(n) is Θ(nc * logk(n)) where c = logb(a), (for some k ≥ 0), then time complexity is Θ(nc * log(k + 1)(n))
- If f(n) is Ω(nc), where c > logb(a), if a * f(n/b) ≤ k * f(n) for some constant k < 1 and sufficiently large n, then time complexity is Θ(f(n)).
Let’s look at examples for each.
## Example 1:
T(n) = 2T(n/2) + nHere, a=2, b=2, and f(n)=n. We have c = logb(a) = log2(2) = 1. In this case, f(n) = n = nc, so we are in the second situation of the Master Theorem. Thus, the time complexity is:
$$\begin{aligned}
Θ(n^c * log^{(k+1)}(n)) = Θ(n * log(n))\end{aligned}$$
Here, k=0 as there no log term with f(n).
## Example 2:
T(n) = 2T(n/2) + log(n)Again, a=2, b=2 but this time f(n)=log(n). Thus c, still 1<log(n) which means we are in the first situation of the Master Theorem. Hence, the time complexity would be Θ(nlogb(a)) = Θ(n).
## Example 3:
T(n) = 2T(n/2) + n^2Here, a=2, b=2, and f(n) = n2. Hence c = 2 > logb(a) = 1. Following the rules of Master theorem, we are now in the third case of the Master Theorem. For that, we must ensure that a * f(n/b) ≤ k * f(n). We find that f(n/b) = n2/4 and a * f(n/b) = 2 * (n2/4) which is 1/2 * n2 that is less than n2 for sufficiently large n. Thus, the Master theorem applies here and the time complexity is Θ(f(n)) = Θ(n2).
Please note that the Master Theorem covers many, but not all, recurrences. There can be situations where the given form does not meet any condition of the Master Theorem.