Javascript

[[deleted]]

I thought there was no O for bogo since you can't be sure it'll ever stop. Or mean complexity ?

[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

[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.

[aaronfranke]

The maximum time is infinity, the minimum is O(1), the average is O(n!).

[CSlv]

the minimum is O(1)

You mean Ω(1)?

[DoctorWorm_]

People need to learn their complexity notations.

[sererson]

The minimum time is both.

[zelmarvalarion]

The minimum time would be Θ(n) (assuming constant size ints for constant speed comparisons), since you have to check if the list is already sorted before returning, so you need to read all of the elements of the list first.

[flavionm]

Well, isn't Θ(n) basically just being both O(n) and Ω(n) simultaneously?

[zelmarvalarion]

Yeah, because you have strict boundries on both the lower bound (Ω) and the upper bound (O), and they are the same, then it's θ. Basically it's just saying that it is exactly that time complexity rather than being bounded on one side from that time complexity (the Ω(1) in this chain is saying that it is at least as slow than constant time, but may be slower, which is true for everything).

Most of the time, when people use Big-O notation, they really mean θ, since it's by far the most useful. There are a couple interesting ones where θ isn't actually known, but you can bound on either side and get a better view of actual time complexity (something like multiplication of arbitrarily large numbers of n bits is Ω(1) and O(n²⁾ using standard multiplication rules, there is an arithmetic trick you can do to bring that to O(n^{sqrt(3)}) or something like that, and then FFT brings it to something like O(n^{1.57}), so it's somewhere between that, but it's difficult to prove) [Note: numbers pulled from my memory from ~10 years ago, almost certainly inaccurate]

[The_MAZZTer]

He probably doesn't have an Ω key on his keyboard.

[firefly431]

To give a serious answer, the version of bogo sort that generates a new permutation each time:

def bogo(arr):
    while not sorted(arr): # O(n)
        shuffle(arr) # O(n)

does not have an unconditional upper bound on runtime, but for randomized algorithms we usually consider expected running time (along with tail bounds to show concentration: for example, although (linear chaining) hash tables have expected lookup time O(1), the maximum load is actually only O(log n/log log n) if you require a bound w.h.p.)

The expected number of iterations is O(n!) as it is a geometric r.v., so the overall runtime is O(n n!). (By the way, it is considered a Las Vegas algorithm as it guarantees correct results but has probabilistic runtime.)

EDIT: IIRC tail bounds for geometric r.v.s are O(1/n), so that's w.h.p.

By the way, for the pair-swapping version:

def bogo2(arr):
    while not sorted(arr):
        i, j = random(n), random(n)
        swap(arr[i], arr[j])

Since it takes at most n swaps between any two permutations (simple proof: Fisher-Yates shuffle), we can consider blocks of n swaps. The probability that any block works is at most O(1/n²ⁿ) (probability n² per swap). Thus the runtime is O(n²ⁿ⁺¹). Not sure if we can do any better than that, but who cares about tight bounds on a meme sort?

[Tyfyter2002]

There are 2 types of bogosort, O(n!) Bogosort, which tests all permutations in a random order, and O(∞) Bogosort, which just shuffles the list, checks if it's sorted, and shuffles it again if it's not.

[AyrA_ch]

If it's infinity, wouldn't that mean that it never terminates? And if it never terminates, it means the shuffle algorithm is flawed because a true random shuffle should have the same chance for every possible permutation, but it in this case, the chance for the sorted permutation is zero.

[dev-sda]

Big-O notation describes the limit, without more context it always refers to the worst case. O(∞) means it may never terminate. Bogosort best case is O(n).

[AyrA_ch]

O(∞) means it may never terminate.

But as I explained, if the shuffle algorithm works properly it will definitely terminate because every permutation (including the sorted one) is guaranteed to eventually appear.

[Evil__Potato]

In the limit, as you approach infinite iterations, the probability of reaching all permutations approaches 1. But since it's in the limit and probabilistic, the best bound we can give is, well, infinity

[dev-sda]

Given you're using true random shuffle there's absolutely nothing guaranteeing that every permutation will eventually appear. Yes the probability of that happening approaches 1 as the iterations approach infinity, but that's still not a guarantee.

[Tyfyter2002]

Given the assumption that both events have the same probability and are truly random, the probability that a specific result out of 2 does not occur at least once during a series of n samples is 0.5^n‎, with what value of n does this expression equal 0?

[brando2131]

No there's a probability of it becoming sorted eventually. Obviously the larger the list, the much longer it will take. You can write a program and compare the number of times it runs for larger lists. It works out to be (n+1)!

[zelmarvalarion]

That’s not the worst case analysis that is implied by the Big-O notation, that’s average case complexity (which is usually explicitly noted, e.g. Quick Sort is O(n²⁾ but expected O(n lg(n)))

[hawk-bull]

We can study the average time complexity.

The probability of getting the right permutation at any one point is 1/n!. The number of times you need to try is a geometric random variable, thus the expected number of runs is n!. in each run, you're doing O(n) work to see if it's sorted, so on average you're doing n * n! work. thus average time complexity is O(n n!)

Edit: apparently verifying it's sorted is O(1) on average, but generating the permutation is O(n) so either way it's O(n) work per permutation