0

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)'?

Arpan Mukherjee
  • 1
  • 1
    What is the time complexity of computing a multiplied by b? Do you consider it to be O(1) or O(ab)? – Adriano Aug 20 '15 at 05:37
  • Yes, obviously it is O(1), but your argue is not logical as according to your logic if the recurrence relation is T(n) = T(n-1) + n, then the solution will be simply a constant as if we must ignore the sum and take it as O(1) instead of the final solution as O(n^2). But it's not true na... – Arpan Mukherjee Aug 20 '15 at 06:06
  • $O(n!)$ is not the same thing as $O(n^n)$, by the way. – Eric M. Schmidt Aug 20 '15 at 07:07

1 Answers1

2

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$

Eric M. Schmidt
  • 3,717