87

Given this sort algorithm how do you express its time complexity?

Originally presented here (partial archive).

#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7
0

8 Answers 8

48

O(max(input)+n)

The complexity just appears awkward to express because most sorting algorithms are data agnostic. Their time scales with the amount of data, not the data itself.

FWIW, as pointed out here, this is not a reliable algorithm for sorting data.

5
  • 3
    I think it needs to be O(max(input)+n) where is the amount of inputs. If it takes longer to iterate through all inputs than the time it takes to process the largest one then O(max(input)) would be incorrect no?
    – yarian
    Jun 24, 2011 at 22:32
  • 2
    You can reduce the complexity by normalizing the data. Divide all inputs by max(input).
    – keyboardr
    Mar 18, 2017 at 1:01
  • 9
    That gives you a big-O bound on the wall-clock time (although it should maybe be O(n log(n)) to take into account the scheduler's work). But unlike most sort algorithms, this one leaves the CPU idle for some of the time, so the complexity in CPU time is O(n) to iterate and start the sleeping threads / processes, plus O(n log n) CPU time in the scheduler to manage the queue of next-to-wake. i.e. O(n log n) CPU time is the throughput cost, but O(max(input) + n log (n)) wall-clock time is the latency cost. Nov 26, 2017 at 5:20
  • max input is a constant so doesn't O(max(input) + n) simplify to O(n)?
    – justinhj
    Jan 11, 2022 at 18:24
  • 1
    No, max input is not a constant. It varies independently of n. So, it must be included in big O.
    – DU_ds
    Feb 6, 2022 at 7:29
32

It depends on how those sleeps are implemented. Ultimately they end up in a scheduler somewhere, and the operational complexity will depend on the scheduling algorithm used. For example, if the sleeps are put as events in a priority queue you will likely end up with something equivalent to heapsort, with complexity O(n log n). A naive scheduling algorithm might result in O(n²).

1
  • The implementation of sleep is an implementation detail that does not directly affect the time complexity of the sort (apart from as a side effect of having large number of sleeps will reduce accuracy or delay). Change from a heap sort to a unsorted list you will delay the speed of the scheduler but not the fundamental characteristics of the "algorithm".
    – justinhj
    Jan 11, 2022 at 18:21
26

I think paxdiablo is nearest, but not for the right reason. Time complexity ignores issues on real hardware such as cache sizes, memory limits and in this case the limited number of processes and the operation of the scheduler.

Based on the Wikipedia page for Time complexity I'd say the answer is that you can't determine the runtime complexity because if it is defined as:

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.

Then we can't talk about the runtime complexity of this algorithm because time which the elementary operations take is so vastly different, that the time taken would differ by more than a constant factor.

2
  • 4
    "Time complexity is commonly estimated by ..." but does not have to be defined by counting elementary operations. It is quite possible to talk about the time complexity of algorithms which sleep for a certain length of time; you can count the amount of time they sleep for, and apply asymptotic analysis to that.
    – kaya3
    Nov 19, 2019 at 4:40
  • Complexity does not ignore issues of real hardware. It is a theoretical result INDEPENDENT of the hardware. Time complexity is not necessarily about physical time. The answers by blahdiblah should and hammar are better. Jan 11, 2022 at 15:30
18

Both the time complexity and the process complexity of that algorithm are O(braindead):

  • With a sufficiently large value in the data set, you'll be waiting for an answer until the sun explodes (264 seconds is a little over half a trillion years).
  • With a sufficiently large data set size, you'll (a) hit your process limit; and (b) find that early sleeps will finish before the latter ones begin, meaning the set (2,9,9,9,9,9,...,9,9,1) will not sort the 1 and 2 correctly.

Time complexity is irrelevant in this case. You can't get any less optimised than "wrong". It's okay to use complexity analysis to compare algorithms as the data set size changes, but not when the algorithms are ludicrous in the first place :-)

1
  • 2
    To make it keep working, you need to scale up the sleep times so that the minimum difference in time between consecutive numbers is greater than the time to queue all the sleeps. This is probably O(n log n) assuming an efficient wake-queue algorithm in the kernel. I think this still boils down to O(n log n) CPU time, with possibly extremely bad wall-clock time. Nov 26, 2017 at 5:24
3

I'm with Jordan, except that I think the wall-clock-time complexity is better expressed as O(2^m) where m is the size of each item, rather than O(max(input)).

If each item has size m, the largest item will have the integer value 2^m (minus one, but nobody cares about that). By construction, the algorithm requires the set-up time to be smaller than 1, a constant.

So wall-clock-time complexity O(2^m), operation-count complexity O(n).

A modified algorithm taking into account set-up time would likely have wall-clock-time complexity O(2^m + n). For instance, it could note the current time at the beginning, calculate base_time = start_time + k*len(list) (for some appropriate constant k), then have the threads sleep until time base_time+i. Then k*len(list) is clearly O(n) and i is O(2^m) as before, for a total of O(2^m+n).

2

If you read the thread you'll see that your question is already answered. The time complexity is O(max(input)) and the operational complexity (number of operations) is O(n).

1
  • 3
    There is an answer the thread sure, but I don't know if it is right
    – justinhj
    Jul 5, 2011 at 7:21
2

Though looks like linear, I think the complexity is still O(log(n) * max(input)).

When we talk about asymptotic time complexity, it means how much time is taken when n grows infinitely large.

A comparasion-based sorting algorithm cannot be faster than O(n * log(n)), and the Sleep-Sort, is actually comparasion-based:

The processes sleep n seconds and wake. The OS need to find the least remaining sleeping time from all the sleeping process, and wake the one up if it's about time.

This will need a priority queue, which takes O(logN) time inserting an element, and O(1) finding the minimum element, and O(logN) removing the minimum element.

When n gets very large, it will take more than 1 second to wake up a process, which makes it larger than O(n).

0

O(max(n, max_i)), where n is the number of items to sort and max_i is the max value of any item in the input array. But sort algorithm not efficient practically.

1
  • Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
    – Community Bot
    Mar 22 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.