Изменения

# Если выпал «Орёл» то перейти на уровень выше и вернуться к шагу <tex>2</tex># Иначе , иначе закончить операцию вставкиэлемента

Таким образом, если использовать честную монету, то математическое ожидание количества элементов на втором уровне равняется <tex>\dfrac{n}{2}</tex>, на третьем уровне <tex>-</tex> <tex>\dfrac{n}{4}</tex> и т.д. На уровне <tex>\log{n}</tex> у нас окажется один элемент. Ну и соответственно Cоответственно вероятности попасть элементу на второй уровень — это <tex>\dfrac{1}{2}</tex>, на третий <tex>\dfrac{1}{4}</tex> и т.д. Вероятность попасть на уровень <tex>\log{n}</tex> равна <tex>\dfrac{1}{n}</tex>.

Используя монетку с распределением отличным от <tex>\left\{\dfrac{1}{2}, \ \dfrac{1}{2}\right\}</tex>, можно влиять на количество элементов на верхних уровнях. Так, например, при использовании монеты с распределением <tex>\{p,q\}</tex> (с вероятностью <tex>p</tex> выпадает «Орёл») математическое ожидание количества элементов на уровне <tex>k</tex> равно <tex>n \cdot p^k</tex>. Таким образом, время поиска будет равно <tex>O\left(\dfrac{k1}{qp} + nq^k\right)</tex>. Соответственно при честной монетке и <tex>log_{\log(frac{1}{p}} {n} \right)</tex> уровней получаем оценку, полученную ранее.

* <tex>\{0, 1\}</tex> {{---}} <tex>O(k+n)</tex>* <tex>\{1, 0\}</tex> {{---}} <tex>\infty</tex> (если разрешить добавление новых уровней при проталкивании элемента после броска монетки; иначе <tex>O(n)</tex>)