The GATE Grind

GATE 2020 CS – Question 16

Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple choice

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

  1. $\Theta(n^4)$
  2. $\Theta(n^2)$
  3. $\Theta(n^2\log n)$
  4. $\Theta(n^3)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\Theta(n^2\log n)$

Explanation

Each insertion costs $O(\log(\text{size}))$, and the size stays between $n$ and $n^2+n$, so each insertion is $\Theta(\log n)$. Total is $\Theta(n^2\log n)$.