October 26, 2023
October 26, 2023
October 26, 2023
###### Asymptotic-Complexity
October 26, 2023
 Question 16
Which is not true about an AVL tree of n nodes?
 A Average space complexity is O(n) B Average space complexity is O(log (n)) C Worst space complexity is O(n2) D Average insert complexity is O(log (n))
Question 16 Explanation:
The space complexity of an AVL tree is O(n) in both the average and the worst case because the AVL tree is balanced BST and will require space almost equal to the space required by complete binary tree which is O(n). But the average space complexity can never be O(logn) since no. of elements are n.
Also time complexity for inserting an element in AVL tree is O(logn) since the tree is balanced binary search tree whose height is O(logn).
Question 16 Explanation:
The space complexity of an AVL tree is O(n) in both the average and the worst case because the AVL tree is balanced BST and will require space almost equal to the space required by complete binary tree which is O(n). But the average space complexity can never be O(logn) since no. of elements are n.
Also time complexity for inserting an element in AVL tree is O(logn) since the tree is balanced binary search tree whose height is O(logn).