1
$\begingroup$

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?      

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks Luke, but can you shed some light on the accepted answer of this link: stackoverflow.com/questions/1379929/recurrence-relation is it any correct? $\endgroup$ – Breakpoint Feb 4 '20 at 13:52
  • 1
    $\begingroup$ Both parts of that answer are correct. The first part describes the running time of the algorithm to compute $n!$, as Luke just did. The second part describes the value of $n!$ $\endgroup$ – Rick Decker Feb 4 '20 at 15:11
  • 1
    $\begingroup$ All of this, assuming unit cost arithmetic. $\endgroup$ – Yuval Filmus Feb 4 '20 at 15:14
  • $\begingroup$ @RickDecker does it mean that the recurrence relation in my question gives upper bound on value of 'n' and the answer of LukeMathieson gives upper bound on time complexity of function? $\endgroup$ – Breakpoint Feb 5 '20 at 15:40
  • 1
    $\begingroup$ @Breakpoint. Yup. To be more precise, the recurrence relation in your question gives the exact value of the function on input $n$ and Luke's gives the time complexity. $\endgroup$ – Rick Decker Feb 5 '20 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.