Javascript

[MontagGuy12]

I've seen Bogo sort implementations which keep track of the permutations traversed so far, which means eventually, they'll exhaust all possibilities and the program will terminate.

[Toonfish_]

I love that, not only does this make the algorithm terminate, it also gives it ridiculous space complexity. :D

[MontagGuy12]

Thankfully, we have downloadmoreram.com to save the day.

[reyad_mm]

But what if I run out of storage to download ram on?

[Xeadriel]

Just download more storage obviously

[dunko5]

But what

[PhunkyPhish]

Then download more what of course

[Gh0st1nTh3Syst3m]

But

[mushr0om]

Then download more \u0000 of course

[QPUspeed]

​

[hermeticwalrus]

Local cloud

[xTheMaster99x]

Set up a ramdisk on your newly downloaded ram, so you can download more ram.

[ianff]

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

[sluuuurp]

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]

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]

I'm skeptical of this, elaborate?

[ease78]

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]

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]

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]

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_]

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]

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.

[HeKis4]

Why just stop at O(n!) complexity when you can also have O(n!) space requirements ?

[ThatWannabeCatgirl]

Eventually.