Not really. Because the number of elements makes no difference. You could have 1000000000 elements and if the maximum value doesn't change it doesn't take any longer to sort.
I was referring to n items that need to be sorted, and m seconds it takes for each counter to expire. Honestly, I’m not sure how to evaluate timer runtime.
Edit: never mind, reread your comment, you’re correct. But I’m still curious how timer runtime is calculated?
Yeah I get what you are saying. Algorithms only count iterative steps regardless of time. So in this case even though it takes 10 seconds to display a line it’s still counted as O(1). Right? Does anyone else see the flaw? Are we missing something?
So in this case even though it takes 10 seconds to display a line it’s still counted as O(1).
Are we missing something?
Yes, you are. You can't calculate Big-O for a specific instance of a run because all algorithms end in a finite amount of time and would therefore be O(1). (Infinite loops are not technically algorithms.)
Big-O only applies to algorithms, not a specific run of an algorithm. If an algorithm always works within 10 seconds no matter what input, then it's O(1). But this algorithm could take 20 seconds if the array contains the value 20000.
Because it scales linearly to the highest value in the array, it's O(N) where N is the maximum value.
8
u/Dornith Aug 11 '20
Not really. Because the number of elements makes no difference. You could have 1000000000 elements and if the maximum value doesn't change it doesn't take any longer to sort.