Hacker News new | past | comments | ask | show | jobs | submit login

n is some value depending on the size of the input, so if you have a look up table that is O(n), then that memory needs to be initialized somehow. If you have a fixed size lookup table then it is O(1), even if it is big.



Compile time fill a lookup table. Run time read 1 value from it. I call it O(1) in time, O(n) in memory. You call it O(1) in both, right?

Now move the compile time code to runtime.

I call it O(n) in time and memory. What do you call it?

If your say O(n) in time and memory - why is moving the code changing its complexity?

If you say still O(1) - then everything is O(1), thus proving P=NP among other things :)

Either way your interpretation isn't very useful.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: