PHP 7 Data Structures and Algorithms

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 ...