(With apologies in advance to my non-nerdy friends).
My friend and fellow student Dave told me about this nifty little sorting algorithm:
Function BozoSort(array a){
while a.notsorted(){
randomize(a)
}
return a
}
The complexity analysis (ie: how long it will take to run) of that algorithm is kind of strange. The average case is obvious: O(2^n), where n is the number of bits in the array. Best case is also obvious: O(1).
It’s the worst-case complexity that is interesting. In the worst case, Bozo Sort never actually finds the solution. Does that make it O(infinity)? Is it NP-Complete?
Actually, I think the answer is that it isn’t appropriate to apply big-O to Bozo sort: it isn’t guaranteed to find a solution, and as such, isn’t technically considered to be an algorithm.
Edit: I realized the average case is actually worse than 2^n, since there is no guarantee that each guess will only appear once. Also, there’s a wikipedia article on this and related “algorithms”.
the average case is the number of possible sorts. you see, it follows a geometric distribution. you see, each trial is independent, and there is always the same probability of finding the correct value (one divided by the number of possible sorts)
the number of possible sorts is going to depend on the array. if all items are unique, there are n! possibilities. if there are repeats, then the number goes down. if the array is only 0s and 1s, then the “worst” average is when half of the bits are ones, the other half zeros (or the difference between the two is no more than one, such as 50 ones, 51 zeros). thus the average case is n choose [floor (n/2)], or better, if there are signifigantly more ones than zeros.
the mean of a geometric is 1/p where p is the probability of a sucess. the variance is q/(p^2). q = 1-p
the geometric distribution is actually a kind of negative-binomial distribution, but that doesn’t really come into play here…