лично я не разбираюсь

Могу ошибаться, но рандомно выбираются приоритеты, а не ключи. Оценка высоты неявного ДД такая же, как и у явного.

Время работы зависит от высоты, а высота от приоритетов — а они рандомные. Таким образом (по доказанному для ДД с явными ключами), высота будет О(logN), значит, асимптотика на операцию O(logN).

Для фиксированных ключей и приоритетов существует единственное подходящее декартово дерево. Для фиксированных ключей при случайных приоритетах математическое ожидание высоты декартова дерева — log(n).
В случае с неявным ДД в каждый момент времени можно считать, что ключи — позиции элементов в ДД (количество меньших элементов + 1). А значит приоритеты выбраны случайно по отношению к ним (так как мы заранее выбрали случайные приоритеты) и поэтому в каждый момент времени математическое ожидание высоты неявного декартово дерево — log(n).