How do you determine the time complexity of a recursive function?

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 n^log_b(a):

- If f(n) is O(n^c), where c < log_b(a), then the time complexity is Θ(n^log_b(a)).

- If f(n) is Θ(n^c * log^k(n)) where c = log_b(a), (for some k ≥ 0), then time complexity is Θ(n^c * log⁽k + 1)(n))

- If f(n) is Ω(n^c), where c > log_b(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) + n

Here, a=2, b=2, and f(n)=n. We have c = log_b(a) = log₂(2) = 1. In this case, f(n) = n = n^c, 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 Θ(n^log_b(a)) = Θ(n).

## Example 3:

T(n) = 2T(n/2) + n^2

Here, a=2, b=2, and f(n) = n². Hence c = 2 > log_b(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) = n²/4 and a * f(n/b) = 2 * (n²/4) which is 1/2 * n² that is less than n² for sufficiently large n. Thus, the Master theorem applies here and the time complexity is Θ(f(n)) = Θ(n²).

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.