3. Running Time Analysis: Give the tightest possible upper bound for the worst c

Question

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

Explanation / Answer

a) O(logN)

b) O(N)

c) O(1)

d) O(NlogN)

e) O(1)

f) O(logN)

g) O(logN)

Time complexity O(1) indicates a constant running time of the algorithm and O(logN) denotes that the algorithm requires travelling down the tree from root to the leaf nodes and height of a binary tree with N nodes is logN.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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