in Programming
98 views
0 votes
0 votes

Not able to understand the last option.

in Programming
98 views

1 comment

In case of AVL tree we can’t get the skew binary tree as compare  to binary search tree to maintain the height balance property it can’t be skewed . The height of AVL tree always is in $\Theta(logn)$ order .

Now in binary search tree worst case time complexity for insertion for one element is $O(height)$ . But in case of skewed binary search tree the height of tree is $O(n)$ .

So , to insert $n$ element in skewed binary search tree it takes $n*O(n)$$=O(n^{2})$ time in worst case time complexity . Now to sort we just call inorder() function which takes $O(n)$ time . So total time complexity =$ O(n+n^2)=O(n^2)$.

In case of avl tree height is always $\Theta(logn)$ so insert $n$ element it takes $n*O(logn)=O(nlogn)$ time . Now to sort we just call inorder() function which takes $O(n)$ time . So total time complexity =$ O(n+nlogn)=O(nlogn)$.
3
3

Please log in or register to answer this question.

Related questions