Богосорт и O (∞)

Хорошо известный алгоритм богосорта просто перемешивает колоду до тех пор, пока она не будет в порядке

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

Сложность этого алгоритма составляет O (∞).

Во-первых, правильно ли определено O (∞)? Как функция может находиться в пределах постоянного множителя бесконечности?

Во-вторых, существуют ли другие хорошо известные рандомизированные алгоритмы с такой сложностью наихудшего случая? (конечно, никто никогда не стал бы использовать богосорт ...)

Наконец, для рандомизированного алгоритма мне кажется, что большую часть времени мы можем говорить только об ожидаемой сложности. Когда имеет смысл использовать big-Oh со случайными алгоритмами?