# Equivalent values

$$\mathcal{O}(f (n)· L) = \mathcal{O}(f (n)\log n)$$

Where is $$L$$ is a depth of tree.

How happened that $$\ L = \log n$$? Why this two values are equal?

The question probably means a balanced tree. In a possibly unbalanced tree, $$L=O(n)$$.
Now, we have our balanced tree. Let's fill it up to a full tree (each level fully filled). At level $$n$$, it has $$2^n$$ nodes (1 on root level, 2 on first child level, etc.) Now, recall that a full tree has a very specific shape - by induction, one may prove that in a full binary tree, $$L_{full}=\lg n$$. But we have defined the new full tree as having the same depth as our base tree, so $$L=L_{full}$$. Thus, $$L=\lg n_{full}$$. But, by definition, $$n\le n_{full}<2*n$$, so $$n_{full}=\Theta(n)$$. And $$\lg \Theta(n)=\Theta(\lg n)$$. Thus, $$L=\Theta(\lg n)$$.
• Strange, I saw at Jeff Erickson book that unbalanced tree had L = O(nlogn) as well. One question: why do you use log base 10 in your example? Is it important? – raviga May 17 at 8:40
• @raviga according to my knowledge, $\ln x$ means natural logarithm, $\log x$ means decimal logarithm in common context and binary logarithm in IT context and $\lg n$ always means a binary logarithm. A tree cannot have $L=O(n \lg n)$, because the length of the path is limited by the number of nodes minus 1, which is $L=O(n)$ – Top Sekret May 18 at 9:22