2
$\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$

2 Answers 2

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$
5
  • $\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, 2020 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$ Feb 4, 2020 at 15:11
  • 1
    $\begingroup$ All of this, assuming unit cost arithmetic. $\endgroup$ Feb 4, 2020 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, 2020 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$ Feb 5, 2020 at 17:52
0
$\begingroup$

Note that $$T(n) = n * T(n-1)$$ compute $n!$ in recursive manner, is differ from running time of your algorithm, hence $T(n)$ is recursive formula for compute $n!$.

If $f(n)$ be the time complexity of your algorithm, so

$$f(n)=f(n-1)+O(1).$$

Note that, if we change your recursive code as follow:

 fact(n)
    {
     if(n == 1)
     return 1;
     else
     for i=0 to n
     x=x+n*fact(n-1);
     return x;
     }

then $f(n)$ will be

$$f(n)=nf(n-1)+O(1).$$

$\endgroup$
3
  • $\begingroup$ No, your algorithm has the same complexity as the original one: once the first return statement in the loop executes, the function, well, returns, skipping the rest of the loop. $\endgroup$ Aug 25, 2021 at 17:59
  • $\begingroup$ If you want something sensible with $\Omega(n!)$ running time, try fact(n) { if(n == 0) return 1; r = 0; for i=1 to n r = r + fact(n-1); return r; } $\endgroup$ Aug 25, 2021 at 18:02
  • $\begingroup$ And now, besides x being uninitialized, it does not compute $n!$ anymore, but $(n+1)!n!/2$. The correct code is in my comment above. $\endgroup$ Aug 26, 2021 at 6:51

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.