GATE CS 2020 Q6 — Trees

To find the worst-case time complexity of inserting $n^2$ elements into an AVL tree that initially contains $n$ elements, we analyze the cost of each individual insertion:

1. AVL Tree Property: An AVL tree is a self-balancing binary search tree. The height of an AVL tree with $k$ elements is always $\Theta(\log k)$.
2. Cost of a Single Insertion: Inserting an element into an AVL tree of size $k$ takes time proportional to its height, which is $\Theta(\log k)$.
3. Total Cost of $n^2$ Insertions:

   As we insert $n^2$ elements one by one, the size of the tree grows from $n$ to $n + n^2$. Let $i$ be the index of the insertion ($1 \le i \le n^2$). When inserting the $i$-th element, the number of elements in the tree is $n + i - 1$.

   The total time complexity $T(n)$ is the sum of the insertion costs:

   $$T(n) = \sum_{i=1}^{n^2} \Theta(\log(n + i))$$
4. Asymptotic Analysis:

   For any $i$ in the range $[1, n^2]$, the size of the tree $k = n + i$ satisfies:

   $$n < n + i \le n^2 + n$$

   Taking the logarithm on all sides:

   $$\log n < \log(n + i) \le \log(n^2 + n) < \log(2n^2) = 2\log n + 1$$

   Thus, for all $i$, we have $\log(n + i) = \Theta(\log n)$.

Substituting this back into the sum:

Therefore, the worst-case time complexity is $\Theta(n^2 \log n)$.