Question

Q5 Match the following operations to their corresponding worst case time complexities Operations Finding the nert larger item in a Hash Table Time Complexities од) O (log n) O(n) O(n log n) O(n2) o(n3) O(n + m) O(m logn) O((n +m) log n) O(n2+nm) Trying to remove a non-eristing item from a Hash Table 2 3Finding the previous smaller item in a possibly unbalanced BST Updating a previous value into a new value in an AVL Tree Sorting m edges in an EL by increasing weights Converting a graph stored in an AM into an AL Counting the number of components of an undirected graph 6 7 8 Finding shortest path(s) from a -> b in an unweighted graph 9 10Finding shortest paths between any pair a, b in a weighted graph Finding shortest path from a ->b in a weighted tree

Answer 1

1) O(n), as we need to iterate all the element
2) O(1), returns null if item cannot be removed
3) O(n), as tree is unbalanced , we need to iterate all the element
4) O(logn), finding the value and then updating it which will take logn time
5) O(mlogn) to sort m edges
6) O(n²) , we need to visit all the entries in matrix
7) O(n+m) i.e using DFS will gives us number of component
8) O(mlogn)
9) O(n+m)
10) O(m)logn)


Thanks, PLEASE COMMENT if there is any concern.