[gpfault]

It's more like O(max(input)), not O(n) (see the first response)

[davrosthedalek]

You can always scan through the array, rescale everything by 1/max(input). Then the sleep part is O(1) and the scan part is O(n) -> O(n) total.

[JoshTriplett]

Division isn't O(1) for arbitrary values (potentially larger than a machine word).

[pdw]

The same is true for comparison though, isn't it?

[dalke]

Sleep maxes out at 2147483647 = 2^31 seconds. Generally these problems assume the transdichotomous model, where the machine word size matches the problem size.

[fennecfoxen]

Well. Let's distinguish between computational complexity and wall-clock time. The code you write yourself here performs operations with O(n) asymptotic complexity where n is the number of elements, but the system scheduler may be able to find additional work to do while the algorithm is waiting to resume, or even put the CPU into a lower-energy state.

Of course, making lots of system calls to create processes and store them in your operating system's process table almost certainly invokes operations with greater than O(n) asymptotic complexity, but this complexity is still unrelated to max(input).