Complexity of recursive factorial program

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.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)