• 0 Posts
  • 4 Comments
Joined 1 year ago
cake
Cake day: November 30th, 2023

help-circle



  • Except the point of this post is that a different sort with worse Big O could be faster with a small dataset.

    The fact that you’re sorting those 64 ints billions of times simply doesn’t matter. The “slower” sort is still faster in practice.

    That’s why it’s important to realize that Big O notation can be useless for small datasets. Because it can actually just be lying to you.

    It’s actually mathematical. Take any equation:

    y = x^2 + x

    For large x the squared term dominates. The linear may as well not exists. It’s O(x^2). But when x is below 1? Well suddenly that linear term is the more important one! Below 1 it’s actually O(x) in practice.