Сложность алгоритма, содержащего рандомную операцию

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

Ответ

Да, можно. Следует оценивать с учётом вероятности.
Например, сложность bogosort оценивается как
я имею массив чисел и хочу вытащить оттуда любое, условно, четное. Но перебирать их буду не по-порядку, а рандомно, в бесконечном цикле, пока не найду нужное.
Если в массиве около половины чисел чётные, то O(1). Если только одно число чётное, то O(n) с жирненькой константой. Если ни одного, то алгоритм вообще не завершится.
Если рассматривать случайный (равномерный) массив, то, вероятно, будет сводиться к O(1) - как доступ по ключу хэш-таблицы.
PS: Провёл эксперимент для случая с единственным искомым числом (результат смотреть в реальной консоли, открытой до запуска сниппета; при запуске браузер может зависнуть на несколько секунд):
function go(n) { while (Math.random() * n | 0); } var res = []; function check(n) { var t = performance.now(); go(1< x+y) } } console.table(res.map(stat));

При удвоении длины время увеличивается вдвое, т. е. действительно O(n).