Thank you! Objective: The objective of this discussion is to study the differenc
ID: 3726992 • Letter: T
Question
Thank you!
Objective: The objective of this discussion is to study the difference in the complexity between the Unsorted List ADT and Sorted List ADT regarding the implementation of their member functions. Feel free to comment on the complexity of any three member functions of your choice for both implementations (ie., Unsorted List ADT and Sorted List ADT) ration Unsorted List Sorted List MakeEmpty LengthIs IsFull ResetList GetNextItem Retrieveltem O(N) Linear search: O(N) Binary search: Olog2N) InsertItem Find Put Combined O(N) O(N) O(N) DeleteItem Find Remove Combined O(N) O(N) O(N) 0(N) O(N)Explanation / Answer
Unsorted and Sorted List ADT has basic difference, that is Sorted List is having elements arranged either descending or ascending order. This is key point in deciding complexity of member function of Unsorted and Sorted List ADT.
Lets go to three member function and see how it is getting each complexity.
1. GetNextItem
Since both cases having complexity of Order 1. It means it take same time in getting next element. It is becuase in getting next item in list is indepent of how list is arranged in both case.
Example: Suppose Unsorted List is A=[2,4,1,6,3,5] and Sorted List is B=[1,2,3,4,5,6]
Lets apply GetNextItem member function, current index is 0.
Apply this member function to A and B, first iteration from A is 2 and from B is 1
2. RetrieveItem
It can have complexity of order N in both case or log2N in case of sorted list. it is because in sorted list one can compare with sorted data in list
Example: Suppose Unsorted List is A=[2,4,1,6,3,5] and Sorted List is B=[1,2,3,4,5,6]
Lets apply RetrieveItem member function first on Unsorted List. Suppose I want to get element 5. For getting this element I have traverse full list in unsorted list.
For in sorted list I will do binary search, since I want element 5, Ill check with middle element since it is greater than left part of list I'll goto right hight hand side and actually I have discard half list which is order of log2N
3.InsertItem
Since unsorted list we can insert item anywhere even at the front of list which is not possible in sorted list because one has to traverse full list to make decision where to insert item. That is why unsorted having complexity of order 1 and while sorted list having complexity of order N.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.