Analysis of a Recursive Function

Performing an analysis of a recursive function is not all that different from performing an analysis of a non-recursive function. We are still going to use the same methodology to find a formula that will represent the number of operations required for a given data size. We will then use that formula to find a curve that best describes the resource usage growth rate.

Analysis of Factorial function

How would we perform an analysis on the following piece of code?

unsigned int factorial(unsigned int n){
    unsigned int rc = 1 ;              //base case result
    if(n > 1)                 //if n > 1 we  have the recursive case
        rc= n * factorial(n-1);  //rc is n * (n-1)!
    }
    return rc;
}

Start by declaring our mathematical variables and functions

Let $n$ represent the number we are finding the factorial of

Let $T(n)$ represent the number of operations it takes to find n! using our recursive function

Similar to iterative version of our code, we will simply count our operations:

unsigned int factorial(unsigned int n){
    unsigned int rc = 1 ;        // 1
    if(n > 1)                    // 1

        rc= n * factorial(n-1);  // 3 + number of ops done by factorial(n-1)

                                 // There are 3 operators, but it also
                                 // calls factorial(n-1) so we must count
                                 // not just 3, but also all ops done by 
                                 //factorial(n-1)
    }
    return rc;                    //1
}

Now... by definition $T(n)$ represents the number of ops needed to our function (factorial) requires when given $n$as its argument. But this also means that $T(n-1)$ would represent the number of ops needed by our function to find (n-1)! (ie number of operations performed by our function when n-1 is passed in as the argument.

Thus, we can actually rewrite our count summary as follows:

unsigned int factorial(unsigned int n){
    unsigned int rc = 1 ;        // 1
    if(n > 1)                    // 1

        rc= n * factorial(n-1);  // 3 + T(n-1)
    }
    return rc;                    //1
}

Now... how do we solve this though? So, lets start by looking at our base cases. If n <= 1, we do exactly 3 operations:

unsigned int rc = 1 ;
n > 1
return rc;

In otherwords, we can say the following:

$T(0) = 3 \\ T(1)=3$

Remember that $T$is a function that represents how many operations our function requires to find factorial of the argument n. So if argument was 0, it takes 3 ops, if argument was 1, it takes 3 ops also. Notice how the analysis of this coincides with the base case of the recursive function

For n >= 2, we do the following 6 operations + we need count number of ops in the recursive call:

unsigned int rc = 1 ;   <--- 1 op
n > 1                   <--- 1 op
return rc;              <--- 1 op
rc= n * factorial(n-1)  <--- 3 operations, =, * and - ... also need to count
                             number of ops done by factorial(n-1)

Thus, we can write the expression as following for the general $T(n)$for n >=2

$T(n) = 6 + T(n-1)$

Now... by definition T(n) represents the number of ops needed to find n! using our function. But this also means that T(n-1) would represent the number of ops needed to find (n-1) factorial using our function. Thus,

$T(n) = 6 + T(n-1)$

by the same token, we can say that

$T(n-1) = 6 + T(n-2) \\ T(n-2) = 6 + T(n-3)$

etc...

In other words T(n-1) = 6 + number of operations done by factorial(n-2). Similarly T(n-2) = 6 + number of operations done by factorial(n-3)

The above statement is true for all values of n >= 2. However, we also know that:

$T(1) = 3$ and $T(0) = 3$

Thus, what we have is:

\begin{align*} T(n) &= 6 + T(n-1) \\ &= 6 + 6 + T(n-2) \\ &= 6 + 6 + 6+T(n-3) \\ ... \\ T(n) &= 6 + 6 + 6 + .... 6+ 3 \end{align*}

There are a total of (n-1) 6's.We know this because we need to reach T(1) to get the 3.

Thus:

$T(n) = 6(n-1) + 3 = 6n-3$

Thus, $T(n)$ is $O(n)$