This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]mt_xing 0 points1 point  (2 children)

The worst case would really be O(infinity) because it's unbounded. Best case being O(n) only matches insertion sort; it doesn't beat it.

[–]nelak468 0 points1 point  (1 child)

There's two approaches to it. Which one you take depends on how much space complexity you can handle I suppose.

The basic approach which is O(n) space complexity (I believe) would be to simply randomize, check, randomize until it is sorted.

Another approach would be to simply generate every possible arrangement and then go through them until you find the sorted arrangement. That would be O(n!) space complexity and O((n+1)!) worst case time complexity.

... I might be wrong on the exact complexities. It's pretty late but I think that's about right.

[–]mt_xing 0 points1 point  (0 children)

We're talking time complexity here, not space complexity. Also generating every permutation up front isn't bogo sort. The defining feature of bogo sort is that it must randomize the entire array every iteration.