Answer : C
Steps: For worst case (in worst case insertion will cause $\Omega(\log n)$ operations in an AVL tree where $n$ is the number of nodes present.
- $1^{st}$ insertion time complexity $= \Theta(\log n)$
- $2^{nd}$ insertion time complexity $= \Theta(\log(n+1))$
- $\vdots$
- ${n^2}^{th}$ insertion time complexity = $\Theta(\log(n+n^{2}-1))$
Total number of operations $= \Theta(\log n) + \Theta(\log (n+1)) + \ldots + \Theta(\log(n+n^{2}-1))$
$\qquad \qquad \qquad= \Theta\left( \log \left(n.(n+1).(n+2)\ldots (n+n^2-1) \right)\right)$
$\qquad \qquad \qquad = \Theta\left(\log n^{n^2}\right)$ $(\because $ the highest degree term in the $\log$ expression will be $n^{n^2}.$
$\qquad \qquad \qquad = \Theta\left(n^2 \log n\right).$