What is the worst case time complexity of inserting $n^2$ elements into an AVL-tree with $n$ elements initially?

An AVL tree is a self-balancing binary search tree. For an AVL tree containing $k$ elements, the height is $\Theta(\log k)$, and the worst-case time to insert one element (including necessary rotations) is $\Theta(\log k)$.

When inserting $n^2$ elements into an AVL tree initially containing $n$ elements:

• For the $i$-th insertion ($1 \le i \le n^2$), the tree contains $n + i - 1$ elements, taking $\Theta(\log(n + i))$ time.

• The total time complexity is:

  $$T(n) = \sum_{i=1}^{n^2} \Theta(\log(n + i))$$

Bounding the sum:

Hence, the overall worst-case time complexity is $\Theta(n^2 \log n)$, which corresponds to option (C).