Circle the most appropriate efficiency class for each of the following data stru

Question

Circle the most appropriate efficiency class for each of the following data structure operations. Each question has exactly one best answer. check if a binary search tree is empty 0(1) 0(1) amortized O(log n) O(n) O(m) O(n log n) O(n^2) O(m + n) O(deg(v)) erase an element from an AVL tree 0(1) 0(1) amortized O(log n) O(n) O(m) O(n log n) O(n^2) O(m + n) O(deg(v)) insert an element into an AVL tree 0(1) 0(1) amortized O(log n) O(n) O(m) O(n log n) O(n^2) O(m + n) O(deg(v)) Hash table search operation 0(1) 0(1) amortized O(log n) O(n) O(m) O(n log n) O(n^2) O(m + n) O(deg(v)) Given a graph with 10,000 vertices and 500 edges. Which graph implementation yields the highest efficiency in terms of execution time for the operation "Erase Vertex"? Edge list Adjacency matrix Adjacency list Edge list or Adjacency list Edge list or Adjacency list matrix All three are equal

Explanation / Answer

1. O(n)

Time Complexity: O(n)
Auxiliary Space : O(1) if Function Call Stack size is not considered, otherwise O(n)

2. O(Logn)

The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Updating the height and getting the balance factor also take constant time. So the time complexity of AVL delete remains same as BST delete which is O(h) where h is height of the tree. Since AVL tree is balanced, the height is O(Logn). So time complexity of AVL delete is O(Logn).

3. O(Logn)

The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Updating the height and getting the balance factor also take constant time. So the time complexity of AVL insert remains same as BST insert which is O(h) where h is height of the tree. Since AVL tree is balanced, the height is O(Logn). So time complexity of AVL insert is O(Logn).

4. O(1)

Hash tables suffer from O(n) worst time complexity due to two reasons:

However, it is said to be O(1) average and amortized case because:

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.