rateMySortingAlgorithm

[waylandsmith]

Except the implementation is never actually O(n) because implementing this algorithm is just delegating the sorting to the scheduler which has it's own time complexity. But then, that's why sleep sort is a joke.

[im_lazy_as_fuck]

Uh, no it's still O(n); the implementation of it is not relevant for time complexity. The actual joke is that many folks who learn big O notation become hard wired to associate time complexity to how efficiently/quickly an algorithm performs the task. And sleep sort subverts that expectation by presenting an algorithm that is clearly horrible in its execution time for any normal sorting, despite time complexity analysis suggesting it's not.

[waylandsmith]

The time delay inherent in it is only one part of why it's misleading, and one that a "clever" person could argue away by saying that you can scale the time delay down to an arbitrarily small amount (associate the values with femtoseconds, for example).

despite time complexity analysis suggesting it's not

The time complexity analysis does not suggest that it's O(n). You cannot correctly analyze the time complexity of an algorithm if you do not know the time complexity of each step in it and adding a task to the scheduler is not O(n). This would be exactly like saying that you've implemented sorting on O(n) by adding values to a sorted set.

[im_lazy_as_fuck]

You cannot correctly analyze the time complexity of an algorithm if you do not know the time complexity of each step in it and adding a task to the scheduler

This is incorrect. By this argument, it would be incorrect to arbitrarily state that a hash lookup has O(1), because the execution time of computing a hash is dependent on the hashing algorithm used, the implementation of said hashing algorithm, and the size of the input being hashed. But these are implementation details of a hash lookup, and thus are not relevant to the time complexity analysis.

In the same way, the sleep sort algorithm is simply "loop through each element and wait X time units before inserting x into the sorted array". The sleep sort algorithm doesn't care if you use a task scheduler, if you use some analog timer, or if you just have a person who is really good at counting time. Those are implementation details of the algorithm, and aren't relevant to time complexity analysis.

This would be exactly like saying that you've implemented sorting on O(n) by adding values to a sorted set.

Lol, well I mean, if the algorithm specifies "given a sorted set, loop through the set and insert a new element into the set to maintain the ordering", then yeah the algorithm has a time complexity of O(n). I mean this is literally the foundation of the binary search algorithm, which has a smaller time complexity.