Big O Notation – Explained as easily as possible

Re:Big O Notation – Explained as easily as possible by d0mine on Sunday January 17, 2021 @03:27AM (#25809144)

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

[ Parent | on HN ]

Re:Big O Notation – Explained as easily as possible by crashocaster on Sunday January 17, 2021 @03:56AM (#25809265)

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

[ Parent | on HN ]

Re:Big O Notation – Explained as easily as possible by d0mine on Sunday January 17, 2021 @05:55AM (#25809751)

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

[ Parent | on HN ]

Re:Big O Notation – Explained as easily as possible by kaba0 on Sunday January 17, 2021 @10:40AM (#25811543)

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.

[ Parent | on HN ]