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.
Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$
algorithms;data structures;binary trees;search trees
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}