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

 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.