Instead of worst case, give the BEST CASE running time for each operation. 3. Ru
ID: 3716295 • Letter: I
Question
Instead of worst case, give the BEST CASE running time for each operation.
3. Running Time Analysis: Give the tightest possible upper bound for the worst case running time for each operation listed below in terms of N. b) O(NlogN): Find the maximum value in a binary min heap. c) O(1): Pop from a Stack implemented with linked list nodes. d) O(NlogN): Given a binary search tree containing N integers, create an AVL tree containing the same values. You should not destroy the original BST in the process. O(1): Pushing a value onto a stack implemented as an array. Assume the array is of size 2N. e) f) O(N): Findmin in a Priority Queue implemented with a binary search tree g) O(logN):Given a binary min heap, what is the worst case runtime of a single insert operationExplanation / Answer
a)O(Logn).--The rotation operations (left and right rotate) take constant time as only a few pointers are being changed there. Updating the height and getting the balance factor also takes 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).
b)O(1)--finds the min (or max or other sortable property) in O(1) time - it’s the value at the top of the heap. *Inserting* (or deleting) N elements will take O(log N) each, so finding the max will take NlogN - whereas simple inspection will take O(N).
c)O(1) -- for push, pop , top of the stack
for search in the stack it is O(N)
d) best case running time of BST operations is O(log N)
e)O(1) --The worst case is O(N) for inserting and deleting, because we may need to resize the array. The amortized case and best case is O(1) for both operations
f) Best case (completely balanced BST) › FindMin, DeleteMin, and Insert (k) are all O(logn) for BST implementation of a Priority Queue
g)O(1)--The number of operations required depends only on the number of levels the new element must rise to satisfy the heap property, thus the insertion operation has a worst-case time complexity of O(log n) but an average-case complexity of O(1)