12

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?

1
  • 3
    I prefer Quantum Bogosort, which is O(n). May 2 '11 at 3:36
8

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.

9
  • 2
    But I thought the definition of big-Oh was worst-case time? May 1 '11 at 8:09
  • 3
    @Eric: No, no, no. That's just a myth. Big-Oh means it is an upper bound. Of what is up to you to say. You can put upper bounds on best and average cases. You can put upper bounds on whatever you want (that actually has one). en.wikipedia.org/wiki/Big-oh May 1 '11 at 8:18
  • 4
    O(∞) does not mean "not bounded" Technically, everything is O(∞) since infinity is always a bound. Just like O(n) is in O(n^2). Its why we use theta
    – Philip JF
    May 1 '11 at 10:11
  • @Philip: Technically, nothing is O(∞), because O(∞) is meaningless. ∞ is not a number. Anyway, I rephrased my answer to make my point clear. May 1 '11 at 15:25
  • @Martinho: You are missing Philip's point. Even if O(infinity) was meaningful, your statement that it is used for algorithms without an upper bound on running time is incorrect. Technically even 1 is O(infinity) in that case. Note that BigOh is used to state upper bounds.
    – Aryabhatta
    May 1 '11 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.