Recurrence relation and time complexity of recursive factorial

Question

I'm trying to find out time complexity of a recursive factorial algorithm which can  be written as:  

fact(n)
{
 if(n == 1)
 return 1;
 else
 return n*fact(n-1)
 }

  So I write the recurrence relation as  

T(n) = n * T(n-1)

  Which is correct according to this post: Recurrence relation of factorial   And I calculate the time complexity using substitution method as follows:  

T(n) = n * T(n-1)  // Original recurrence relation
= n * (n-1) * T(n-2)
...
= n * (n-1) * ... * 1
= n!

  But according to this post, here, both recurrence relation and time complexity are incorrect.   What am I doing wrong or not getting correctly?      

Answer 1

Your understanding of how recursive code maps to a recurrence is flawed, and hence the recurrence you've written is "the cost of T(n) is n lots of T(n-1)", which clearly isn't the case in the recursion. There's a single recursive call, and a multiplication of the result.

Assuming the numbers aren't large, the multiplication is constant time, and it's a single operation, not a multiplier on the number of recursive calls:

$$ T(n) = T(n-1) + c_{1} $$

The base case is $T(1) = c_{2}$

If we simplify things further, and assume $c_{1} = c_{2} = 1$ (it makes no difference to the final asymptotic analysis anyway), you get:

$$ T(n) = T(n-1) + 1 = T(n-2) + 1 + 1 = T(n-2) + 2 ... $$

And the same final result as the StackOverflow question of $T(n) = n$.