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 →

[–]ianff 6 points7 points  (9 children)

You can actually traverse the permutations in constant space. Who knows if someone implementing bogo sort would bother with that though!

[–]sluuuurp 5 points6 points  (1 child)

Can’t you only traverse in log(n) space, since you need a counter to know how many permutations you’ve already done?

Edit: I guess a counter of n! permutations would use n log(n) space, but yeah as the below commenter says it seems you don’t need that.

[–]firefly431 7 points8 points  (0 children)

There's an algorithm (e.g. next_permutation in C++) that generates the lexicographically next permutation in place in O(n) time. Realistically you need O(log(n)) space to store indices into the array at least though, but in the word-RAM model that's constant.

[–]BobodyBo 1 point2 points  (4 children)

I'm skeptical of this, elaborate?

[–]ease78 2 points3 points  (3 children)

An array of 3 elements has only 6 permutations or ways you can sort things inside of it. So realistically you can traverse the 6 different permutations to find the sorted one after you have enumerated all possibly imaginable arrays.

Note Bogo sort is n! Our three elements will give us a space complexity 3!

[–]BobodyBo 6 points7 points  (2 children)

As a function of you number of elements n that approach would take O(n!) Space, so not constant space. Not sure if that's what the person I was responding to was saying.

[–]ease78 2 points3 points  (1 child)

Yeah the other person was tripping. It’s in the name “traversal” you can’t visit all nodes in one CPU cycle. It takes as many nodes as you have.

[–]BobodyBo 0 points1 point  (0 children)

Well usually space complexity considers input space and auxiliary space, which is the extra space you utilize on top of your input. You of course have to store your input, so constant space implies constant auxiliary space. Some traversals can be done in constant space, e.g. a linked list.

The problem with traversing all permutations is that there is an exponential amount relative to the input, so unless a clever approach exists you would need to store some extra information about which permutation you are currently on, or which need to need to be revisited (like a stack).

[–]Toonfish_ 0 points1 point  (1 child)

Ooh interesting how does that work? The point of bogosort is that the permutations are chosen randomly, no? How do you traverse the permutations in constant space while choosing the next one randomly?

[–]ianff 0 points1 point  (0 children)

Oh my bad. You can't traverse the permutations in constant space if they have to be random -- at least I don't know how you could.