2
$\begingroup$

I am reading about B-Tree through CLRS. One of the exercise problem is to express maximum number of keys in a BTree of height $h$ and minimum degree $t$.

Properties of BTree of $t$:

  • $t\ge 2$
  • Min. no of keys in a node is $t-1$ and max. number of keys in a node is $2t-1$
  • Max number of children a node can have is $2t$

To solve it the formula I came up with is $$\sum_0^h (2t)^h(2t-1) $$

Does it have any convergence?

Improve this question
$\endgroup$
2
  • $\begingroup$ convergence doesn't seem to be the precise term. $\endgroup$
    – greybeard
    Commented Feb 2, 2020 at 7:52
  • 1
    $\begingroup$ @greybeard that was the closes term that I could think of. Maybe reduction?? $\endgroup$
    – Sab
    Commented Feb 2, 2020 at 7:59

1 Answer 1

Reset to default
2
$\begingroup$

Found it (using geometric serie for the sum)

$$\sum_{i=0}^h (2t)^i(2t-1) = (2t-1) \sum_{i=0}^h (2t)^i = (2t-1) \frac{(2t^{h+1}-1)}{(2t-1)} = (2t)^{h+1}-1 $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.