GATE Computer Science (CS) 2020 Solved Papers

Question : 13 of 65

Marks: +1, -0

What is the worst case time complexity of inserting

{n}^{2}

elements into an

{AVL}

Tree with

{n}

elements initially?

$θ( {n}^{2} \log {n})$
$θ( {n}^{2})$
$θ( {n}^{3})$
$θ( {n}^{4})$

Validate

Solution:

Insertion of an element into

{AVL}

requires

{O}(\log {n})

time.
To insert an element
1. Find the position, where to insert
2. After insertion, to satisfy AVL properly, we may need to perform rotation.
So, (1) take 'log n time' and (2) take 'log

{n}

' time.
Total time for inserting one element into AVL tree is

\log n+\log n=2 \log n ⇒ O(\log n)

Now, To insert

{n}^{2}

elements

⇒ {n}^{2} \log {n}

⇒ O(n^{2} \log n)

Go to Question:

Prev Question

Next Question