Analysis of recursive algorithms depends on the type of recursion we are using. If it is linear, the complexity will be different; if it is binary, it will have a different complexity. So, we do not have a generic complexity for the recursive algorithms. We have to analyze it on a case-by-case basis. Here, we will analyze factorial series. First, let's focus on the factorial part. If we recall from this section, we had something like this for factorial recursion:
function factorial(int $n): int {
if ($n == 0)
return 1;
return $n * factorial($n - 1);
}
Let's assume that it will take T(n) to compute factorial ($n). We will focus on how to use this T(n) in terms of the Big O notation. Each time we call the factorial function, there are certain steps involved:
- Every time, we are checking the base case.
- Then, we call factorial ($n-1) on each loop.
- We do a multiplication with $n on each loop.
- Then, we return the result.
Now, if we represent this using T(n), then we can say:
T(n) = a when n = 0
T(n) = T(n-1) + b when n > 0
Here, both a and b are some constants. Now, let's generate a relationship between a and b with n. We can easily write the equation as follows:
T(0) = a
T(1) = T(0) + b = a + b
T(2) = T(1) + b = a + b + b = a + 2b
T(3) = T(2) + b = a + 2b + b = a + 3b
T(4) = T(3) + b = a + 3b + b = a + 4b
We can see that a pattern is emerging here. So, we can establish that:
T(n) = a + (n) b
Alternatively, we can also say in simple terms that T(n) = O(n).
So, the factorial recursion has a linear complexity of O(n).