# 17.5 B-Tree Performance

## B-Tree Runtime Analysis

To consider the runtime of B-Trees, let $$L$$ be the maximum items per node. Based on our invariants, the maximum height must be somewhere between $$\log\_{L + 1} N$$ (best case, when all nodes have $$L$$ items) and $$\log\_2 N$$ (worst case, when each node has 1 item).&#x20;

The overall height, then, is always on the order of $$\Theta(\log N)$$

<figure><img src="https://content.gitbook.com/content/17YWK4wlHXK38A55HuVr/blobs/JN1xM4GcRKdSpfPNfnWg/image.png" alt=""><figcaption><p>Worst-case B-Tree height</p></figcaption></figure>

<figure><img src="https://content.gitbook.com/content/17YWK4wlHXK38A55HuVr/blobs/NRInDdIKsgMK9ukpuWZB/image.png" alt=""><figcaption><p>Best-case B-Tree height</p></figcaption></figure>

### Runtime for `contains`

In the worst case, we have to examine up to $$L$$ items per node. We know that height is logarithmic, so the runtime of `contains` is bounded by $$O(L \log N)$$. Since $$L$$ is a constant, we can drop the multiplicative factor, resulting in a runtime of $$O(\log N)$$.

### Runtime for `add`

A similar analysis can be done for `add`, except we have to consider the case in which we must split a leaf node. Since the height of the tree is $$O(\log N)$$, at worst, we do $$\log N$$ split operations (cascading from the leaf to the root). This simply adds an additive factor of $$\log N$$ to our runtime, which still results in an overall runtime of $$O(\log N)$$.
