!rant, cool anyway

  • 5
    There's even a RosettaCode article on it 😂 https://rosettacode.org/wiki/...
  • 6
    so, that would mean that it would be O(n)?
    since it would be simply the length of time of the largest value in the array?
  • 5
    @tisaconundrum Good ol' StackOverflow to the rescue on this question.

    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.

  • 4
    @tisaconundrum it would be O(max(n))

  • 4
    The complexity is O(?) because the 'n' is sleeping.

    Just kidding.. I think the real complexity is
    Err I ment
  • 1
    It is more something like O(sum(array content)).
    It can't be expressed by n, but now n is taken into account because it is used by the sum.

    A simple example is, is that the array [1 2 3], is faster to sort than the array [1 2 10000].
  • 3
    @micfort no, it's more like max(n) since all the sleeps are subprocessed and run concurrently (sorta, theyre is the delay of execution which also makes the algorithm unreliable)
  • 2
    @brettmoan normally, concurrency is not taken into account when analyzing the complexity of an algorithm. Thats one of the drawback/afvantage of such an analysis. The only thing taken into account is in which order of complexity are number of instructions. Assuming that sleep(x) can be done in O(x), then this algorithm takes O(sum(content array)). But sleep instruction is actually no instruction, then it can be derived to O(n).

    The concurrency is not taken into account because some algorithms are better suited for concurrency than others, and in some different kind of concurrency can be introduced. This is really difficult to generalize. Also if you can create the optimal concurrency for every algorithm, then you have the original problem back. So in the complexity analysis you won't take into account concurrency.
  • 0
    @ng1905 We need this!!! 😂😂😂
Add Comment