17 ms·
What freshman complexity class would teach you to conflate how fast an algorithm is in practice with the asymptotic complexity?
by whimsicalism 3y ago
What freshman complexity class would teach you to conflate how fast an algorithm is in practice with the asymptotic complexity?
- CaptainNegative 3y agoNot to mention that QuickSort isn't a single algorithm but rather a class of algorithms (as the choice of pivot is left unspecified), and there are methods to choose the pivot that give O(n log n) worst case or O(n log n) expected running time (e.g. median of medians or soft heaps for the former, random choice for the latter).
- yjftsjthsd-h 3y agoMost of them? If the instructor doesn't call out the difference and point out that all terms of a O() expression have invisible but important constants tacked on, it's easy to accidentally conflate scaling complexity with actual total speed.
- bee_rider 3y agoWhy would the instructor skip that part of the the definition? Giving out wrong definitions as a prank or something?
- yjftsjthsd-h 3y agoThey're not intentionally avoiding it, they just get caught up in the mathematical angle and only mention its (dis)connection to real execution time in a passing comment if at all. Or they might even mention that there are constants in play... and then say that of course since they're constants we can ignore them for the purposes of O() notation. It's the difference between learning from PHDs and engineers, I suppose.