Dark Mode

8,299 views

15 votes

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

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

edited
Dec 30, 2021
by Mohitdas

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

0

0

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

1

26 votes

Best answer

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

edited
Aug 30
by [ Jiren ]

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

2

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

0

6 votes

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.

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.