Data Structure for Spaghetti algorithm
a) if you use an unsorted array as the data
structure, what would the big-O cost of each delete-max operationbe?
b) what would the total big-O cost of the algorithmbe?
c) if you use a heap or balanced binary search tree asthe data structure, what would be the big-O cost of each delete-maxoperation be?
d) what would the total big-O cost of the algorithmbe?
Answer
a)
Using array data structure delete-max will take O(n) time,because to find maximum we have n-1 comparisons and then to deletein worst case (if maximum is present at first position) it
OR
OR