Почему длина списка уменьшается до sqrt (n) после каждого сравнения в поиске с интерполяцией?

Согласно книге, которую я читаю, интерполяционный поиск занимает в среднем O (loglogn) .
В книге предполагается, что каждое сравнение сокращает длину списка с n до sqrt (n) . Что ж, нетрудно вычислить O (loglogn) с учетом этого предположения.
Однако в книге больше не говорится об этом предположении, за исключением того, что в нем говорится, что это правильно.

Вопрос: может ли кто-нибудь объяснить, почему это так?