program for factorial with time complexity less than o(n) | Sololearn: Learn to code for FREE!

+4

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

8/31/2018 11:40:16 AM

hank

+13

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

+6

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.

+5

Oma Falk what do you mean, lol?

+5

+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

+4

upps... nonsense

+4

Kishalaya Saha f4 here https://code.sololearn.com/c3A818bmOSGM/?ref=app

+3

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

+3

check for zero

+3

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.

+2

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

+2

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

+1

works only for numbers up to 12, but is a purely mathematical solution https://code.sololearn.com/c49Q17Nx2jsV/?ref=app

0

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.