Exercise 2 For this problem you will submit a text document that contains your a
ID: 3741595 • Letter: E
Question
Exercise 2 For this problem you will submit a text document that contains your answers and a justification for why you picked your answer How much time is needed in Big-Oh notation for each of the two operations, insert and search, for an unsorted array-list with n elements? Same as above, but with a sorted array-list. Assume that insert will use binary search (You may have to do a little research into Big-Oh for binary search) NOTE: THIS IS AN ARRAY-LIST, not a LinkedList, is there a difference? 1. 2.Explanation / Answer
1.
Unsorted Arraylist:
Insert : O(1) [constant time], since the arraylist is unsorted we can simply add an item to arraylist.
Search : O(n) [linear time], since the arraylist is unsorted, we used to search element using linear search, which takes O(n) time.
Sorted ArrayList:
Insert : O(n) [linear time] since the arraylist is in sorted order, we need to find the right place and insert an item.
Search : O(log n), since the arraylist is in sorted order, we can use binary search to search an item, which takes O(log n) time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.