4 ms·

"sorting with O(n^2) is no longer a bottleneck as we have fast processors" /s

• itissid 4y ago
  That makes no sense. Just the brutal math of a polynomial is always going to be poor enough to notice than subpolynomial times.
  • vitiral 4y ago
    Often but not always. Cool trick: any bounded limit is always O(1)! Pick a small enough bound and an O(n^2) algorithm behaves better than an O(n log n). This is why insertion sort is used for sorting lengths less than ~64, for example.
    • Dylan16807 4y ago
      Pick a small enough bound and certain O(n^2) algorithms will behave better than certain O(n log n) algorithms. Big O notation doesn't take into account constant factors of overhead or plain old once-per-run overhead.
      • vitiral 4y ago
        Sorry it was indeed a typo