Complexity of recursive factorial program

complexity-theory factorial
Karan picture Karan · Feb 24, 2010 · Viewed 65.5k times · Source

What's the complexity of a recursive program to find factorial of a number n? My hunch is that it might be O(n).

Answer

Alex Martelli picture Alex Martelli · Feb 24, 2010

If you take multiplication as O(1), then yes, O(N) is correct. However, note that multiplying two numbers of arbitrary length x is not O(1) on finite hardware -- as x tends to infinity, the time needed for multiplication grows (e.g. if you use Karatsuba multiplication, it's O(x ** 1.585)).

You can theoretically do better for sufficiently huge numbers with Schönhage-Strassen, but I confess I have no real world experience with that one. x, the "length" or "number of digits" (in whatever base, doesn't matter for big-O anyway of N, grows with O(log N), of course.

If you mean to limit your question to factorials of numbers short enough to be multiplied in O(1), then there's no way N can "tend to infinity" and therefore big-O notation is inappropriate.

Related questions

Example of O(n!)?

What is an example (in code) of a O(n!) function? It should take appropriate number of operations to run in reference to n; that is, I'm asking about time complexity.

Read More
Complexity of factorial recursive algorithm

Today in class my teacher wrote on the blackboard this recursive factorial algorithm: int factorial(int n) { if (n == 1) return 1; else return n * factorial(n-1); } She said that it has a cost of T(n-1) + 1. Then with iteration method she …

Read More
Example of a factorial time algorithm O( n! )

I'm studying time complexity in school and our main focus seems to be on polynomial time O(n^c) algorithms and quasi-linear time O(nlog(n)) algorithms with the occasional exponential time O(c^n) algorithm as an example of …

Read More