0

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

dantopa
  • 10,342
calm27
  • 117

1 Answers1

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

Top Sekret
  • 239
  • 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? – calm27 May 17 '19 at 08: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 '19 at 09:22