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.
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.
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.
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.
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.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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.
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.
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.
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.
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.