Да, можно. Следует оценивать с учётом вероятности.
Например, сложность 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<<n);
t = performance.now() - t;
(res[n] = res[n] || []).push(t);
}
for (var q=1; q<14; ++q)
for (var w=0; w<10000; ++w)
check(q);
function stat(a) {
return {
min: Math.min(...a),
max: Math.max(...a),
sum: a.reduce((x,y) => x+y)
}
}
console.table(res.map(stat));

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