# 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). 

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

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2F91Ssy8VWI5VfprxVcNfN%2Fimage.png?alt=media&#x26;token=03341862-d55b-47ea-a81a-e336b61db3d9" alt=""><figcaption><p>Worst-case B-Tree height</p></figcaption></figure>

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2FIz1soxD54sJkbIdVc1UM%2Fimage.png?alt=media&#x26;token=679b97ea-fa1d-47ee-9de6-cf576e309223" 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)$$.