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?