Question 16

An AVL tree is a height-balanced binary search tree. The time complexity of inserting a single element into an AVL tree containing $k$ nodes is $\Theta(\log k)$ in the worst case (involving $O(\log k)$ comparisons to find the insertion position, plus at most two tree rotations taking $O(1)$ time).

When inserting $n^2$ elements into an AVL tree that already contains $n$ elements:

• For the first inserted element, the tree has $n$ elements, taking $\Theta(\log n)$ time.
• For the $i$-th inserted element ($1 \le i \le n^2$), the tree contains $n + i - 1$ elements, taking $\Theta(\log(n + i))$ time.
• The total time $T(n)$ across all $n^2$ insertions is:
  $$T(n) = \sum_{i=1}^{n^2} \Theta(\log(n + i))$$

To establish the asymptotic bound:

• Upper bound: Each term satisfies $\log(n + i) \le \log(n + n^2) = \log(n(n+1)) = \Theta(\log n)$. Therefore:
  $$T(n) \le \sum_{i=1}^{n^2} c \log(n + n^2) = c \cdot n^2 \cdot \Theta(\log n) = O(n^2 \log n)$$
• Lower bound: Considering the final $n^2 / 2$ insertions where the tree size is at least $n + n^2 / 2$:
  $$T(n) \ge \sum_{i=n^2/2}^{n^2} c' \log(n + i) \ge \frac{n^2}{2} \cdot c' \log\left(n + \frac{n^2}{2}\right) = \Omega(n^2 \log n)$$
• Combining both bounds yields $T(n) = \Theta(n^2 \log n)$.