Recurrence relation to find time-complexity

Question

I have the following simple C-program:

int factorial(int n)
{
    if(n==0)
        return 1;
    else
        return n*factorial(n-1);
}

Now, if I take the recurence relation as

    T(n) = n*T(n-1), when n>0
    T(n) = 1, when n=1

then, the time complexity of this algorithm becomes O(n!), i.e., O(n^n)

and now, if I take the recurrence relation as

    T(n) = T(n-1) + c, where 'c' is some constant

then, the time complexity of this algorithm becomes O(n)

Which one is correct?

I know, the time-complexity of this algorithm is O(n), but then, how can we ignore the variable 'n' which is multiplied with the function call 'factorial(n-1)'?

Answer 1

The formula describing the time complexity of an algorithm is usually completely different from the formula describing the result of an algorithm. We can see this using some simple examples:

int id(int n)
{
     return n;
}

Here the time complexity is $O(1)$, even though the function returns $n$.

Again, consider

int one(int n)
{
     int result = 1;
     for (int i = 0; i < n; i++)
         result = 1;
     return result;
}

This (silly) algorithm has $O(n)$ time complexity, but always returns $1$.

Now, in your example,

$T(0) = 1$ and $T(n) = nT(n-1)$ for $n>0$

is a recurrence describing the return value of the factorial function, but is not a recurrence describing the running time. For the running time, we need to look at the time which the operations involved take place. In particular, multiplying by $n$ in an algorithm doesn't cause the running time to be multiplied by $n$. Suppose we define $S(n)$ to be the running time of factorial(n). If multiplication is $O(1)$, then, to compute n*factorial(n-1), this is the time to compute factorial(n-1), plus a constant amount, and we arrive at your second, correct, recurrence:

$S(n) = S(n-1) + c$