Ranter
Join devRant
Do all the things like
++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple API
Learn More
Comments
-
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? -
@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.
https://reddit.com/r/programming/... -
bioDan56238y@tisaconundrum
The complexity is O(?) because the 'n' is sleeping.
Just kidding.. I think the real complexity is
O(Zzz)
Err I ment
O(n*n!) -
micfort1378yIt 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]. -
@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)
-
micfort1378y@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.
Related Rants
!rant, cool anyway
undefined
!rant
sort
invent
4chan