News for hackers. Stuff that matters.
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by whimsicalism on Friday May 19, 2023 @11:25AM (#36003058)
What freshman complexity class would teach you to conflate how fast an algorithm is in practice with the asymptotic complexity?
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by CaptainNegative on Friday May 19, 2023 @12:05PM (#36003537)
Not 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).
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by yjftsjthsd-h on Friday May 19, 2023 @12:05PM (#36003542)
Most 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.
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by bee_rider on Friday May 19, 2023 @01:59PM (#36004949)
Why would the instructor skip that part of the the definition? Giving out wrong definitions as a prank or something?
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by yjftsjthsd-h on Friday May 19, 2023 @02:12PM (#36005080)
They'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.