Fill in this table with the worst-case asymptotic running time of each operation

Question

Fill in this table with the worst-case asymptotic running time of each operation when using the data structure listed. Assume the following: Items are comparable For insertions it is the client's responsibility not to insert an item if there is already in the data structure (so the operations do not need to check this For insertions, assume the data structure has enough location (do not include any resizing costs). For deletions, assume we do not use lazy deletion. insert delete getMin get Max take an item take an item (take an item (return and add it to and return if and remove Smallest return it largest the from the item in the tem in the structure) it is in the structure, if structure Structure structure) present in it) unsorted array N/A AVL tree array kept organized as a min-heap (b) shown below, places items in the first list (of the size N) into the second list in reverse order. public void reverse List List original, List reverse reverse. Clear for int i 0; i original size i++) reverse. add(0, original .get i (b.1) What is the running time of reverseList when both lists are ArrayLists? (b.2) What is the running time of reve when original is an ArrayList and reverse is a LinkedList? (c) In terms of big-oh notation, what is the running complexity of the algorithm with the time following recursive relation T(0) 0, T(n) TL3n/4J) Justify

Explanation / Answer

a)

b)

b.1) O(N^2) because the calls to add are O(N) each.
b.2) O(N) because the calls to add and get are both O(1) each.

As per Chegg policy, we are only athorized to provide one answer at a time. Please re-post part C as new question. Thank you!

Please Rate Well! Good Luck!

Insert Find Delete getMin getMax Unsorted Array O(1) O(n) O(n) O(n) O(n) AVL Tree O(log n) O(log n) O(log n) O(log n) O(log n) Array kept organized as a min-heap O(log n) O(n) O(n) O(1) O(n)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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