Изменения

Если в качестве случайного источника мы будем использовать честную монету, то в среднем случае будет <tex>\log{n}</tex> уровне. На самом верхнем уровне будет не более двух элементов. Тогда на каждом уровне в среднем нужно проверить не более двух элементов (в противном случае могли бы вместо двух нижних элементов проверить ещё один уровнем выше). Уровней всего Пусть у нас <tex>\log{n}k</tex>уровней, откуда вытекает оценка времени тогда время работы поиска элемента в <tex>-</tex> <tex>O(k \loglog_k{n})</tex>.