GATE CSE 2020 | Question: 6

Question

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

• A. $\Theta (n^{4})$
• B. $\Theta (n^{2})$
• C. $\Theta (n^{2}\log n)$
• D. $\Theta (n^{3})$

Comments

https://www.cs.odu.edu/~zeil/cs361/web/website/Lectures/avl/pages/avlcomplexity.html

---

One element takes (log n) time to insert.

What is the rebalancing of the AVL tree's operational complexity?

Insertions and deletions in an AVL tree may need (log n) rotations if the tree was maximum unbalanced before the element was inserted. Because you could conduct O(log n) work per each of the n nodes, rebalancing the tree might take O(n log n) time.

For each element inserted or removed, a rotation will be done

AVL tree is a self-balancing Binary Search Tree (BST) where the ... The height of an AVL tree is always O(Logn)

If there are n elements, N rotations will be conducted in the worst case. If there are n+1 elements, a rotation will be executed for that additional element, i.e N+1 rotations.

N*N rotation is possible for n*n elements.

As a result, it will take (n^2 log n ) time to insert n^2 elements after n elements already exist 

---

 with n elements initially

does this mean we are inserting n^2 more elements to it apart from those n elements it have?

And what if this was not mentioned there and we have to directly create an AVL tree with n^2 elements then its TC? 

---

Yes @Pranavpurkar. Here we are inserting more $n^2$ elements into an AVL tree which has $n$ elements in it already.

If there no elements prior, then it would take:-

$log(1)+log(2)+log(3)+...log(n^2)$

$\implies log(1.2.3.4….n^2)$

$\implies log((n^2) \ !)$

$\implies O(n^2log(n^2))$

$\implies O(n^2log(n))$

---

AVL tree is balanced so that if we want to insert 1 element then it will take logn time so if we want to insert $n^2$ element then it will take $O(n^2logn)$ Time

Answer 1

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).$

Comments

@niloyy2012

Actually what's happening is Time complexity of Avl tree is O(log( no of nodes in the tree ))

here when we insert a new node into the tree then no of nodes become n+1 as already n nodes are present in the tree so when inserting second node of n^2 nodes we need time complexity of O(log( no of nodes in the tree )) which is O( log ( n + 1) ) 

like wise when inserting third node we require time complexity of O( log ( n + 2) ) as no of nodes became n + 2

finally Total time required = O( log ( n*(n+1)*(n+2)*....*(n+n^2-1) ) ) 

For last node  Time complexity will be O( n + n^2 - 1 ) because no of nodes present in the tree at the time of inserting last node is n + n^2 - 1 so time complexity = O(log( no of nodes in the tree )) = O( log ( n + n^2 - 1 ) )

---

@jiren Thanks for the detailed explanation. Got it. I misinterpreted the question because I thought out of n^2 elements n elements are already present, that's why I am calculating at the time of n^2th element insertion already inserted element count is = (n^2 – 1).
 

---

For those who are facing difficulty in multiplying the terms:-

$log(n. (n+1).(n+2) … (n^2+n-1))$

$\implies log(\underbrace{n.n.n ….n} (...))$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \  n^2 \ times$

$\implies log(n^{n^2})$ [Because n is being multiplied $n^2$ times]

$\implies O(n^2log(n))$

Answer 2

1st insertion worst case time complexity = O(log n)

2nd insertion worst case time complexity = O( log (n+1) )

and so on...

So worst case time complexity = O(log n) +  O( log (n+1) ) + .... +  O( log (n+$n^{2}$) )

= O(log n*(n+1)*(n+2)*...(n+$n^{2}$))

= O(log f(n))

Maximum degree term of f(n) would be $n^{n^{2}}$ as you can see n would be multiplied $n^{2}$ number of time for sure.

So O(log f(n)) = O( log $n^{n^{2}}$) = O($n^{2}$logn)

So option C is correct.