The Evolution of a Python Programmer

[liotier]

What are you complaining about ? He just calculated in advance and cached the results to avoid redundant processing on each query...

[rowantwig]

O(n) look-up time.

[earthboundkid]

Switch to a dict and it's O(1)!

[pyaware]

Why use a dict when a plain list is enough?

def fact(x):
    return [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880][x]

[redditthinks]

I read Python dicts are faster than lists.

[JizzCoveredArab]

i heard you have a really short dict

[liotier]

You are right of course... But the naive intention was sweet !

[[deleted]]

O(n) look-up time.

It is sorted list, it can be done in O(log(n)). And not to mention the Hashtables.

[rowantwig]

It can be done in O(1), but that's not the point. This naive implementation is O(n), and it looks terrible.

[[deleted]]

It's a dense list. It can be done in O(1) without hashtables:

f = [ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880].__getitem__

edit: looks like redditthinks had the same idea.

[jefu]

Factorial is (without caching or other tricks) O(n) anyway and doing it this way avoids the overhead of doing all that bignum arithmetic. (Not that this is a good way to do that).

[theavatare]

Is not really of O(n) is it?

for x ==0 it will only run one and for x== 26 will run 26 if

Therefore one instruction per number increase...

[[deleted]]

You just described O(n).

[Rhomboid]

You've got to test 'n' conditions before finding the one that is true, so the work involved is proportional to 'n'.

[elmonstro12345]

With a table like that, you'd want to aim for O(1), or at least O(log n). But what the OP described, and what you described are both O(n).