3 ms·

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

• davrosthedalek 12y ago
  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 12y ago
    Division isn't O(1) for arbitrary values (potentially larger than a machine word).
    • pdw 12y ago
      The same is true for comparison though, isn't it?
    • dalke 12y ago
      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 12y ago
  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).