title: Bogosort and O(∞)
body: <p>The well known bogosort algorithm simply shuffles a deck until it is in order</p>
  
  <pre><code>while not inOrder(deck) do
      shuffle(deck);
  </code></pre>
  
  <p>The complexity of this algorithm is O(∞).  </p>
  
  <p>First, is O(∞) well-defined?  How can a function be within a constant factor of infinity?  </p>
  
  <p>Second, are there other well-known randomized algorithms that have this kind of worst case complexity?  (of course no one would ever use bogosort...) </p>
  
  <p>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?</p>