Data Structure and Algorithms: Fill out the table below by giving worst case run
ID: 3673937 • Letter: D
Question
Data Structure and Algorithms: Fill out the table below by giving worst case running time and explain so that I can understand. Thankyou!
Fill in the table below by giving the worst case running time for each one of the indicated operations applied to each indicated data structure of size n. Express the answer in terms of n. . (a) Ins is Insertion of a key r into data structure, (b) Del is Deletion of a record of the data structure pointed by a pointer/reference (for linked structures) or index (for array-based structures) z, i.e. the location that will be deleted is known, . (c) Sea is Search for key r. . (d) FindMin is FindMinimum, i.e. determine and return the value of the key with the smallest value among the keys of the data structure with the key still residing in it . (e) FindMax is FindMaximum, defined similarly to FindMinimum. (f) ExMin is ExtractMin, that is remove and return the key with smallest value. (g) ExMax is ExtractMax, that is remove and return the key with largest value. For removal operations the data structures must be maintained in compact form after the operation (i.e. there are no gaps or locations with no keys) SA Sorted Array (SA) with elements ordered in increasing key order SSL Sorted Singly Linked List (SSL) with the elements in increasing order and the smallest value key pointed by a head pointer; no tail pointer. pointed by a head pointer; no tail pointer new key to be inserted with A1 holding the MAX key. SDL Sorted Doubly Linked List (SDL) with the elements in increasing order and the smallest value key MXH A max-heap stored as an array A1..sizeof(A)), where sizeof (A) , i.e. A is big enough for a Fill entries by writing say n in a box to denote worst case running time of O(n), 1 to denote worst case running time of O(1), and so on. All keys already in data structure are distinct. We fill in the entry for FindMin into an SA. Since it is (1) we write 1 SA SSL SDLMXH Ins(x) Del(z) Sea(x) FindMin ExMin ExMaxExplanation / Answer
SA SSL SDL MXH
Ins(x) O(n) O(n) O(n) log(n)
Del(x) O(n) O(n) O(1) log(n)
Sea(x) log(n) O(n) O(n) O(n)
FindMin O(1) O(1) O(1) O(n)
Findmax O(1) O(1) O(1) O(1)
ExMin O(n) O(1) O(1) O(nlogn)
ExMax O(1) O(n) O(1) O(logn)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.