Big O Notation – Explained as easily as possible

Re:Big O Notation – Explained as easily as possible by sixstringtheory on Saturday January 16, 2021 @02:54PM (#25804933)

> 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

If a language/library can change the dominant asymptotic term of an algorithm like that, instead of just the constant factor, that is a problem. Does that really happen with python or is this exaggeration? I’m inclined to accept another reason to dislike these super high level interpreted langs but I’ve never seen something that e.g. appears written to be logarithmic to become quadratic because of library implementation details.

[ Parent | on HN ]

Re:Big O Notation – Explained as easily as possible by Brian_K_White on Saturday January 16, 2021 @03:29PM (#25805213)

The language doesn't matter, nor even it's high vs low class.

You can write a short function in any language that looks O(1) if you only look at the surface or high level of it. Even assembly. Meanwhile in the middle of that routine is a single call to another function or macro which may be 0(1) or O(n!).

Python was just an example.

[ Parent | on HN ]

Re:Big O Notation – Explained as easily as possible by a1369209993 on Saturday January 16, 2021 @04:15PM (#25805575)

> Even assembly.

Although high-level languages like python or to a lesser but less excusable degree C++ are more susceptible to this because more features can secretly be greater-than-constant-time function calls.

[ Parent | on HN ]