DEV Community

Discussion on: What does "Big-O notation" mean anyway?

Collapse
 
dwd profile image
Dave Cridland

I'm sorry, but I'm going to entirely disagree with the primary premise of your article.

"Big-O" notation is absolutely not about how fast (or "how many steps") your function runs. An O(n²) function can easily outperform an O(log(n)) function, for a given n - as you point out, there's a hidden "k" involved here.

"Big-O" notation is about how the run time will change as the system scales.

So if a function takes 28 seconds to run through with 4 inputs, and it's O(n), it'll take 56 seconds with 8 inputs.

Or, if an O(n²) function takes 9 seconds to run through with 3 inputs, it'll take 81 seconds with 9 inputs.

But knowing that, you can sensibly pick that O(n²) function over the previous O(n) function if you happen to know the input size never goes above 7.

Collapse
 
jvanbruegge profile image
Jan van Brügge • Edited

I did not mean to imply that the computational complexity equals speed. The steps are just to visualize how a piece of code gets executed.
But yeah, I should have added a paragraph emphasizing this and also talk about break even points between two algorithms/datastructures.

Collapse
 
md2perpe profile image
Per Persson

It's not even true that "if a function takes 28 seconds to run through with 4 inputs, and it's O(n), it'll take 56 seconds with 8 inputs". The quoted is more likely true if you replace "4 inputs" with "4 miljon inputs" and "8 inputs" with "8 miljon inputs".

The "Big-O" notation tells how the running time (or consumed memory, whatever it is used for) behaves for big numbers of inputs. For small n the time for a O(n) algorithm is probably not proportional to n.

Collapse
 
dwd profile image
Dave Cridland

Well, yes, or at least sort of. So if an algorithm takes a number of CPU cycles equal to (kn + c), then we call it O(n). For low values of n, the c may dominate, making it not a simple matter of linear scaling. But a typical algorithm has a low value of c.

So the case with 4 million inputs versus 8 million is really only working because the c is just noise at that level.

Luckily, c is going to be pretty small anyway, and much of it will remain constant no matter what the algorithm used - function call overheads, for instance.

Thread Thread
 
md2perpe profile image
Per Persson

An algorithm that is efficient for big n often takes more time for small n than one that is slow for big n. The reason is that the former is more complicated. Also, n is usually small.