4 ms·
> 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 wit
by d0mine 6y ago
> 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?
- crashocaster 6y agoFor some large n, integers in the algorithm may be so large that operations on them cease to be constant time.
- d0mine 6y agothat 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?)
- kaba0 6y agoI 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.