Analyzing recursive algorithms

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:

1. Every time, we are checking the base case.
2. Then, we call factorial...