Верхняя граница времени выполнения для b-дерева

Question

В искусстве компьютерного программирования, внизу страницы 485

Предположим, что есть B-дерево порядка m и N ключей, поэтому на уровне l появляются листья N+1.

Количество узлов на уровнях 1,2,3... не менее 2,2 [м / 2], 2 [м / 2] ^ 2...

(Здесь [] обозначает верхнюю границу)

А кнут дайте

N+1 >= 2[м /2]^(л-1)

---

Мой вопрос:

Разве это не должно быть N+1 >= 2+2[м / 2] +2 [м /2]^2+...+2[м /2]^(l-1)?

Какой смысл принимать во внимание только узлы (l-1) -го уровня?

Answer 1

Узел ветвления с k ключами имеет k + 1 дочерний элемент. Таким образом, как бы много ни было узлов на уровне l - 1, на уровне l должно быть больше узлов.

Таким образом, N + 1 (количество узлов на уровне l) больше, чем количество узлов на уровне l - 1. Очевидно, что фактическое количество узлов на уровне l - 1 больше или равно минимальному количеству узлов на уровне l - 1. Таким образом, N + 1 ≥ 2⌈m / 2⌉^{l - 1}.