Кэш-массив с забывчивым просмотром

Я пытаюсь понять подобный массив упреждающего просмотра кэша, который описан в здесь , и на странице 35 этой презентации

Анализ вставки в упрощенный Фрактальное дерево:

1. Стоимость объединения 2 массивов размера X составляет O (X = B) блоков ввода-вывода. Слияние очень Эффективность ввода-вывода.
2. Стоимость слияния одного элемента составляет O (1 / B), поскольку O (X) элементов были объединено.
3. Максимальное количество раз, когда каждый элемент объединяется, составляет O (logN).
4. Средняя стоимость вставки составляет O (logN / B)

Я могу понять №1, №2 и №3, но могу Не понимаю №4. Из бумаги слияние можно рассматривать как перенос двоичного сложения, например, (31) B может быть представлено: 11111
при вставке нового элемента (плюс 1) должно быть 5 = ​​log (32) слияние (5 переносов). Но в этой ситуации мы должны объединить 32 элемента! Кроме того, если каждый раз мы добавляем 1, то сколько переносов будет выполнено от 0 до 2 ^ k? Anwser должен быть 2 ^ k - 1. Другими словами, одно слияние на вставку!

так как вычисляется №4?