3 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 sixstringtheory 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
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.
- Brian_K_White 6y agoThe 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.
- a1369209993 6y ago> 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.