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

Answer1) O(1)

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

Answer3) Aver­age time com­plex­ity in binary search tree for any oper­a­tion takes O(logn) time but there are times when your tree is skewed. In those cases the oper­a­tions on them takes O(n) time but in AVL Tree, since it is always bal­anced, it always takes O(logn) time.

Answer4) Hash tables are O(1) average and amortized case complexity, however it suffers from O(n) worst case time complexity.

Answer5) Adjacency matrix

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---