# Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$

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.

## 1 Answer

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}

• 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. – Scis May 5 '13 at 16:09
• 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. – Scis May 5 '13 at 16:17
• @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$. – Petr May 5 '13 at 16:26