Data Structures Problem For each function below, give an asymptotic upper bound

Question

Data Structures Problem

For each function below, give an asymptotic upper bound using "big-Oh" notation. Your answer should be as "tight" and "simple" as possible oC) a) f(n)-4n3 + 5n2 log n b) f(n)- 3n + 4 log n+2n OC) c) f(n)-1.6n n5 d) f(n)-2 log log n+ log(n/2) OC) oC) 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) OL): Insert into a Dictionary implemented with an AVL tree b) 0( 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) o): 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 Suppose we sort an array of numbers, but it turns out every element of the array is the same, e.g., {17,17, 17,.., 173. (So, in hindsight, the sorting is useless.) a) What is the asymptotic running time of insertion sort in this case? b) What is the asymptotic running time of selection sort in this case? c) What is the asymptotic running time of merge sort in this case? d) What is the asymptotic running time of quick sort in this casef? e) Give an example input list for which merge-sort and heap-sort take O(n log n) time, but for which insertion sort takes O(n) time. What if the list is reversed?

Explanation / Answer

As per Chegg policy, I am answering only first 4 parts. In order to get the solution of remaining questions, please upload them again.

As per definition of big-oh, f(n) = O(g(n)) iff c*g(n) >= f(n) where c>0 and n>=n0 and n0>=0

a.) f(n) = 4n3 + 5n2 log n = O(n3)

b.) f(n) = 3n + 4 log n + 2n = O(2n)

c.) f(n) = 1.6n + n5 = O(n5)

d.) f(n) = 2 log log n + log(n/2) = O(log n)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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