cross-posted from: https://programming.dev/post/6660679

It’s about asking, “how does this algorithm behave when the number of elements is significantly large compared to when the number of elements is orders of magnitude larger?”

Big O notation is useless for smaller sets of data. Sometimes it’s worse than useless, it’s misguiding. This is because Big O is only an estimate of asymptotic behavior. An algorithm that is O(n^2) can be faster than one that’s O(n log n) for smaller sets of data (which contradicts the table below) if the O(n log n) algorithm has significant computational overhead and doesn’t start behaving as estimated by its Big O classification until after that overhead is consumed.

#computerscience

Image Alt Text:

"A graph of Big O notation time complexity functions with Number of Elements on the x-axis and Operations(Time) on the y-axis.

Lines on the graph represent Big O functions which are are overplayed onto color coded regions where colors represent quality from Excellent to Horrible

Functions on the graph:
O(1): constant - Excellent/Best - Green
O(log n): logarithmic - Good/Excellent - Green
O(n): linear time - Fair - Yellow
O(n * log n): log linear - Bad - Orange
O(n^2): quadratic - Horrible - Red
O(n^3): cubic - Horrible (Not shown)
O(2^n): exponential - Horrible - Red
O(n!): factorial - Horrible/Worst - Red"

Source

  • off_brand_@beehaw.org
    link
    fedilink
    arrow-up
    23
    ·
    11 months ago

    Yup, it’s why O(N+10) and even O(2N) are effectively the same as O(N) on your CS homework. Speaking too generally, once you’re dithering over the efficiency of an algorithm processing a 100-item dataset you’ve probably gone too far in weeds. And optimizations can often lead to messy code for not a lot of return.

    That’s mostly angled at new grads (or maybe just at me when I first started). You’ve probably got bigger problems to solve than shaving a few ms from the total runtime of your process.