b tree least upper bound

Question

Hi I have an university assignment question that I can't fully understand. My tutor doesn't understand some of the terminology and my lecturer in the subject is not particularly forthcoming. The subject is algorithms and data structures in a cs stream, but I'm asking here because it's to do with the maths aspect of the question, and I don't have a maths background.

The question is in two parts: First:

"calculate the number of elements in the barest b-tree of order m=5 and of heights 1,2,3 and 4."

Using the formula n=2K^h -1 elements where K=ceil(m/2), we get :

h      n
1      5
2     17
3     53
4    161

easy-peasy. The next bit I don't understand:

"Use these results to determine the least upper bound for a B-tree of order M=5 which has 100 elements."

I know the maximum number of elements in a B-tree is: (M^(h+1)) -1

so I can modify the table thus:

h    nMIN   nMAX
1      5     24
2     17    124
3     53    624
4    161   3124

So 100 elements can fit into a tree of height 2 or height 3. Now this can be expressed as a subset of heights {1, 2, 3, 4}, namely {2,3} that fulfills the condition. So my question is which is the least upper bound? I think it's 3. But I'm not sure. Or am I completely misunderstanding the question?

Answer 1

Your reasoning looks right to me.

Note that you do not actually need to compute the $n_{\rm MAX}$ column in order to find the upper bound. You know that your tree with $100$ elements cannot have $4$ or more levels, but on the other hand, it can have $3$ levels (because if you start with a minimal tree of $3$ levels and $53$ elements, and keep adding elements to it, it can't possibly grow a level until there are at at least $161$ elements -- so somewhere along the way you must have passed a tree with $3$ levels and $100$ elements).