The cost of finding a leaf in balanced tree (with data only at leaves, which is how we represent integers in base B) of size N is on average proportional to its

The cost of finding a leaf in balanced tree (with data only at leaves, which is how we represent integers in base B) of size N is on average proportional to its branching factor B multiplied by its height H. Height is (log N)/(log B), so cost is B * (log N)/(log B). By derivatives, that's minimized when B satisfies 0 = (log N) (1 / (log B) + B(-1/((log B)^2)(1/B) == 0 = 1/(log B) - 1/(log B)^2 1 = log B Base of the logarithm = B. This looks like you can pick any logarithmic base b you want, and so any B you want, but in fact the derivative I wrote assumes e is the base (hence the term "natural" logarithm. Other bases b would yield a scaling factor of ... e/b, since d(e^x)/dx = e^x and b^x = e^((ln b) x) You can chase "deeper" reasons for this all day long by digging deeper into the the many definitions/properties of e and proving they are equivalent. Playing with e is the most fun you can have in pre/calculus.