Equivalent values

Question

$$\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?

Answer 1

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