Изменения

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