Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Bogosort and O(∞)

The well known bogosort algorithm simply shuffles a deck until it is in order

while not inOrder(deck) do
    shuffle(deck);

The complexity of this algorithm is O(∞).

First, is O(∞) well-defined? How can a function be within a constant factor of infinity?

Second, are there other well-known randomized algorithms that have this kind of worst case complexity? (of course no one would ever use bogosort...)

Finally, for a randomized algorithm, it seems to me that most of the time we can only speak about expected complexity. When does it make sense to use big-Oh with randomized algorithms?

like image 952
Eric Conner Avatar asked May 01 '11 06:05

Eric Conner


1 Answers

O(∞) is an abuse of notation. If we're being strict about the notation, it cannot mean the growth is bounded by a constant factor of infinity, because infinity is not a real number.

If we accept this abuse of notation with its obvious meaning that the growth is "limited above by infinity" it becomes clear that it is too generic to be of much use. After all what function wouldn't be limited by infinity?

Because the worst-case running time of bogosort has no real upper bound, O(∞) is the only thing one can say about it with big-Oh notation, which, as we've seen, isn't really saying much.

But we can still use big-Oh notation when talking about randomized algorithms: we just need to analyse the things about it that have upper bounds. Bogosort has a best case, and that best case runs in O(n) time. And in average, it runs in O(n*n!) time.

like image 174
R. Martinho Fernandes Avatar answered Sep 18 '22 14:09

R. Martinho Fernandes