2
$\begingroup$

We're asked to prove the above mentioned lemma but I having a hard time proving this rigorously.

We did prove that given $n$ values AVL's height is $\Theta\left (\log \left ( n \right ) \right )$ So I thought that after inserting a $\frac{n}{2}$ values the height of the tree will be at least $\Theta\left (\log \left ( \frac{n}{2} \right ) \right )$ which and because each isertion we make is now on a tree with at least $\frac{n}{2}$ and insertion is $\log \left (h \right ) $ where $h$ is the height of the tree.

So for a function $F$ using the previous logic:

$\begin{align} F &= \frac{n}{2} \times \log \left (h \right ) \\& \geq \frac{n}{2} \times \log \left (\frac{n}{2} \right ) \\&=\Omega\left( n\log \left (n \right ) \right) \end{align}$

But I have a few issues with this

  • This does feel fishy to me don't know why but it doesn't feel like a good well defined calculus proof :)
  • I'm not sure which way to take it in order to prove the upper boud i.e $\mathcal{O}$

If I haven't given all the required information I'd be glad to.

$\endgroup$
2
$\begingroup$

The upper bound is easy. Because a tree with $n$ nodes has height $\Theta(\log n)$, when inserting the sequence of elements each tree has height at most $O(\log n)$, so the total complexity is $O(n\log n)$.

You're right with the lower bound. After inserting $n$ elements the tree has height $\Theta(\log \frac{n}{2})=\Theta(\log n - \log 2)=\Theta(\log n)$. So we can split the sum into two and bound each part by its lowest element: \begin{align} \sum_{i=1}^n \Theta(\log i) &= \sum_{i=1}^{n/2} \Theta(\log i) + \sum_{i=n/2+1}^n \Theta(\log i) \\ &= \frac{n}{2} \Omega(\log 1) + \frac{n}{2} \Omega(\log\frac{n+1}{2})\\ &= n\,\Omega(\log n) \\ &= \Omega(n \log n) \end{align}

$\endgroup$
  • $\begingroup$ Thanks for your answer but I have a bit of a problem with the "easy" part, it's not that I do not understand this part, it even seems intuitive to me but I'm having a hard time to phrase it mathematically. $\endgroup$ – Scis May 5 '13 at 16:09
  • $\begingroup$ Actually do you think saying $h\leq \ln\left ( n \right)$ for each step $\rightarrow $ each iteration is $\leq \ln\left ( n \right) $ so $\sum\limits_{i=1}^{n}\ln\left ( i \right) \leq n\cdot \ln\left ( n \right)$ would suffice? I'm sorry I'm very new to CS proofs. $\endgroup$ – Scis May 5 '13 at 16:17
  • $\begingroup$ @Scis Yes, if $a_i\leq b_i$ for every $i$ between $1$ and $n$ then $\sum_{i=1}^n a_i\leq\sum_{i=1}^n b_i$. In our case $a_i=\log i$ and $b_i=\log n$ (doesn't depend on $i$, all $b_i$s are the same) so $\sum_{i=1}^n\log i\leq\sum_{i=1}^n\log n=n\log n$. $\endgroup$ – Petr Pudlák May 5 '13 at 16:26

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.