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

  • $\begingroup$ 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? $\endgroup$ – raviga May 17 at 8:40
  • $\begingroup$ @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)$ $\endgroup$ – Top Sekret May 18 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.