program for factorial with time complexity less than o(n)

Answer 1

I don't know if such algorithm exists, but you can reach O(1) time complexity (sort of...) by using recursion + memoization (dynamic programming).

In other words, calculate the factorials recursively while storing them at a dictionary. So whenever you need them again, simply access them from the dictionary, which is an O(1) operation.

See my code snippet:
https://code.sololearn.com/cSWq4LUuh0fd/?ref=app

Answer 2

Anna time complexity is probably immaterial for such a small range of 1 to 100 or even 1 to 1000. For larger ranges you probably need to consider the trade off between memory (of the dictionary) and time performance.

Answer 3

Oma Falk what do you mean, lol?

Answer 4

VcC could you explain your comment or point to a link?

Answer 5

n! = (2k+1)! 
= 1*2*...*(k-2)*(k-1)*k*(k+1)*(k+2)*...*2k*(2k+1)
= k * ((k-1)*(k+1)) * ((k-2)*(k+2))*...*(1*(2k+1))
= k * (k² - 1²) * (k² - 2²) * (k² -3²) * ... * (k² - (k-1)²)

for odds

Answer 6

upps... nonsense

Answer 7

Kishalaya Saha f4 here

https://code.sololearn.com/c3A818bmOSGM/?ref=app

Answer 8

The function fact(n) itself has a time complexity of O(1). I don't think it's possible without this kind of cheating.

https://code.sololearn.com/cnHlSF13axhB/?ref=app

Answer 9

check for zero

Answer 10

How about extracting all the 2's from factorial? For example,

factorial(12)
= 2^10 * (1) * (1 * 3) * (1 * 3 * 5)
* (1 * 3 * 5 * 7 * 9 * 11)

Each term in parentheses can be used to help find the next term. They are the products of odd numbers up to 12/2^k for k = 3, 2, 1, 0.

Answer 11

The problem with factorial is that the bigger your number the more complex the multiplication. So fact(n) done naively has a n2logn complexity. Using better algorithms you can reach nlogn^3loglogn

Answer 12

See here : the first method is better for large n because divide and conquers reduces the number of huge number multiplications
https://code.sololearn.com/c3A818bmOSGM/?ref=app

Answer 13

works only for numbers up to 12, but is a purely mathematical solution

https://code.sololearn.com/c49Q17Nx2jsV/?ref=app

Answer 14

This code, which I don't understand yet, is faster than math.factorial!!!

https://code.sololearn.com/coJdFXmoQRex/?ref=app

Well, for large numbers (bigger than 1000). For small numbers it's hard to beat library functions, which are probably written in C.

More details: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
This page is pretty much a repository of all factorial algorithms.