2

Is there any way to reduce the time complexity of the factorial function below O(n), and what is the time complexity of its implementation in the math library in python?

Also, is any memorization done for some set of inputs (in Python 3), to further reduce its runtime?

DEEPAK S.V.
  • 85
  • 7
  • There is no way to reduce the time complexity of the factorial function to below O(n), since n! has approximately n log n digits. That's assuming you're interested in wall time, and not the number of (big-int) arithmetic operations. – Paul Hankin Oct 22 '22 at 10:28
  • 1
    I don't believe there's memoization, but factorials of small numbers are precomputed: https://hg.python.org/cpython/file/d42f264f291e/Modules/mathmodule.c#l1396 – Paul Hankin Oct 22 '22 at 10:29
  • see [Fast exact bigint factorial](https://stackoverflow.com/a/18333853/2521214) no You can not go under `O(n)` because fast factorials have big overhead so its meaningless to use them for CPU native datatypes and bigints introduce bigger complexity as most basic math operations are `O(m)` (where `m` is bitwidth of number) or worse ... For example the best I could do for `n!` is `~O(n^1.4)` However for CPU native datatype you can do `O(1)` LUT as only few factorials are possible to fit into 32 or 64 bit ints – Spektre Oct 23 '22 at 06:40

2 Answers2

4

Python uses the divide-and-conquer method for computing factorials.

See if this helps.

esskayesss
  • 88
  • 5
2

If you do not mind floating point precision, math.lgamma(n+1) returns the natural logarithm of the factorial of n.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75