JNU 20182 PhD CS
October 26, 2023AsymptoticComplexity
October 26, 2023JNU 20182 PhD CS
Question 16

Which is not true about an AVL tree of n nodes?
Average space complexity is O(n)


Average space complexity is O(log (n))


Worst space complexity is O(n^{2})


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).
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).
Correct Answer: B
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).
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).
Subscribe
Login
0 Comments