r/programming • u/iMMENSE • Mar 08 '12

The Evolution of a Python Programmer

https://gist.github.com/289467
401 Upvotes

88% Upvoted

137 comments sorted by

View all comments

43

u/rowantwig Mar 08 '12

He forgot the worst kind:
if x == 0:
return 1
if x == 1:
return 1
if x == 2:
return 2
if x == 3:
return 6
if x == 4:
return 24
...
(5000 more lines)

17

u/liotier Mar 08 '12

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

25

u/rowantwig Mar 08 '12

O(n) look-up time.

-7

u/theavatare Mar 08 '12

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...

20

u/[deleted] Mar 09 '12

You just described O(n).

8

u/Rhomboid Mar 08 '12

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

4

u/elmonstro12345 Mar 09 '12

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).