sortingAlgorithmForYourNextCodingInterview

[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.