Hacker News Reader

> If you implement an algorithm in a high level language like Python you may get much worse runtime than you thought because some inner loop does arithmetic with bignum-style performance instead of hardware integer performance

How does it change big O? Typically, you implement "bignum" on top of "hardware integer" regardless of the language. Or do you mean that some common integer operations are implemented with suboptimal big O in CPython?

View on HN

For some large n, integers in the algorithm may be so large that operations on them cease to be constant time.

that is obvious. But how does it change big O? (why any manual implementation would have a better big O compared to existing arithmetics implementation in CPython?)

I think he meant that naively implementing an algorithm may not be bounded by the O notation he/she originally wanted due to code calling other functions “hidden” from the programmer.

Reply on news.ycombinator.com