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

good afternoon,

 

can you point out the mistake in my approach, it would help alot cleaning up my silly doubts.

I think $O(n^{3})$

My approach: since the AVL tree already contains $n$ elements, therefore when $n^{2}$ elements are inserted, the time complexity will grow to $O(n * n^{2}) = O(n^{3})$. Im ignoring $log(n)$ because ... its relatively smaller than $n^{3}$.

😓

 

---

But the question has option O(nlogn) and O(n^2) so ans should be O(n^2)

---

@motab

Total elements to insert: $n^2$

 

1st insertion will take $log_2(n)$

2nd insertion will take $log_2(n+1)$

. . . . 

$n^2$'th insertion will take $log_2(n^2 - 1)$

 

Therefore total time = $log_2(n) + log_2(n+1) + . . . . + log_2(n^2-1)$

= $\theta(log_2(n^{n^2})) = \theta(n^2log_2(n))$

 

[since $log(mn) = log(m)+log(n)$]

---

@Arjun @Sachin Mittal 1 @Deepak Poonia @Shaik Masthan sir I think these answer need some modification bcz

$n^{2}$ insertion will take 

Θ($lg \left (n+n ^2{- 1} \right )$)

Therefore total time complexity =$lg \left (n \right )$+$lg \left (n+1 \right )$+....+....+$lg \left (n+n ^2{- 1} \right )$

= Θ($n^{2}$logn).

---

Fine now?

---

@gatecse yes

---

Can't we simply say thay insertion in AVL tree is of O(log n) and we are inserting $n^{2}$ elements. So the whole operation is of o($n^{2}$ log n) ?

---

@Neel123 Bro Technically you cant say like that because

For every insertion Height of the AVL tree is changing right 

 

 

---

@samarpita @Arjun @Sachin Mittal 1 @Deepak Poonia @gatecse
can anyone please tell me why (n + n^2 – 1) ? will it not be (n^2 – 1) as at the last n^2 ^th element insertion we have already (n^2 -1) element so the value should be log(n^2 – 1)? Am I correct or I miss something?

---

@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.