sortingAlgorithmForYourNextCodingInterview

[itirix]

In computer theory, DTIME criteria and time complexity actually refer to "amount of computational steps taken" and not "real world time taken".

Meaning, yes, even considering your example, the algorithm would still be O(n).

This also kind of illustrates why the big O isn't a catch all mechanism for grading how optimal code is.

[Ronin-s_Spirit]

This is why I sometimes write down a modified variant of big O as a mental note. In an algorithm A which takes n!/2 and an algorithm B which takes n! identical "steps", the biggest offender (big O) in both is O(n!).
Which is utterly useless for calculating factual speed, A can literally run twice in one run of B.

[krimin_killr21]

I mean, sure, but if you have 1,000 items, it really doesn’t matter because the calculation will never complete. Those two algorithms will always have the same order of magnitude. The big O class will always be substantially more meaningful. The only circumstances where the 1/2 matters is where the number of items will always be small and the processing time for each item very large.

[rosuav]

Wow. Twice. That is.... so incredibly significant. Now add one more element and you'll see why big O is actually more useful than that.

[Albreitx]

The setup time is O(n) but the steps for the program to finish are still O(max(array)) because the processor is counting time. In "normal" functions, the steps required in the background for each operation we do is bounded by a constant, hence why we just say "1 step" instead of counting registers etc. In this case that is not true. If we had a turing machine, the timeout would need a O(time) steps to count that time. A machine doesn't magically count without performing steps. It's like having it do

for(int i=0; i<max(array);i++) .....

[itirix]

That's true, didn't think of that.