1. Fill in the following in increasingorder

O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n)

2. Linear search can be done on data in an array or in a list. What is the average time complexity for successful search using an array? Using a list? Name an advantageof the list implementation. Name an advantage of the arrayimplementation.

Linear search on an array is O(1) for a sorted list and O(n) for an unsorted list, while linear search on a list of O(n). Linear search is faster, but has to be presorted. The list can be any order.

3. Binary search can be done on data in a sorted array or in a binary search tree.What is the average time complexity for successful search using the array? Using the BST? What is the worst case time complexity for each? Name an advantage of the BST implementation. Name an advantage of the sorted arrayimplementation.