Please provide a short explanation with each runtime 3. Running Time Analysis: G

Question

Please provide a short explanation with each runtime

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. a) OU ): Insert into a Dictionary implemented with an AVL tree. b) OC ): Find the maximum value in a binary min heap. c) OU ): Pop from a Stack implemented with linked list nodes. d) OL ): 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. e) OU ): Pushing a value onto a stack implemented as an array. Assume the array is of size 2N. f) OL : Findmin in a Priority Queue implemented with a binary search tree g) C ): Given a binary min heap, what is the worst case runtime of a single insert operation

Explanation / Answer

a) O(log n) : As AVL tree is height balanced Insertion will take time equal to height which is log n
b) O(n) : Even though we need to check half the tree, Still it would take n time
c) O(1) : Just remove the head pointer
d) O(n log n) : Creating a AVL tree with N elements takes O(N log n)
AS EACH insertion will take O(log n) time
e) O(1) : Pushing the value alsp takes O(1) time
f) O(n), Just get the left most child of the tree which takes O(n) time
g) O(log n): Inserting in heap takes o(log n) time as the tree is balanced


Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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