1 Binary Search or Linear Search? 50 points Let us analyse the runtime complexity of two algorithms, i.e., linear search (Algorithm A) and binary search (Algorithm B) using experimental method. Algorithm A: Store the list Sin an array or list, in whatever order the values are given. Search the list from beginning to end. If S[i] == r for any value of i, stop searching and return True (i.e., found), otherwise return false. Algorithm B: Store the list S in an array or indexed list (such as the Python list). Sort the list. Use binary search to determine if x is in S. Return True or False as appropriate. When using Algorithm A, searching for a value that is in the list will require an average of n/2 comparisons, while in the worst case, searching for a value that is not in the list will require n comparisons. When using Algorithm B, searching for any value will require an average of about logn comparisons. However, sorting the list will take O(nlogn) time. n = If we are doing a very small number of searches, Algorithm A is preferable. However if we are doing many searches of the same list, Algorithm B is preferable since the time required to sort the list once is more than offset by the reduced time for the searches. This is what complexity theory tells us. Your task is to conduct experiments to explore the relationship between the size of the list and the number of searches required to make Algorithm B preferable to Algorithm A. See the detailed requirement below: 1) Implement two algorithms using Python. When implementing Algorithm B, you must write your own sort function and your own binary search func- tion. You may use any sort algorithm that has complexity in O(nlogn). 2) For n = 1000, 5000, and 10000, conduct the following experiment: Use a pseudo-random number generator to create a list S containing n integers. - For values of k ranging from 10 upwards: Choose k target values, make sure half of which are in S and half are not in S, i.e., modeling the average case - Use Algorithm A and B separately to search the k target values in S. - Design and conduct experiments to determine the approximate small- est value of k for which Algorithm B becomes faster than Algorithm A. Provide a short description on how you determine the smallest value of k and what is the smallest value of k you find. Other requirements: All data structures involved need to be implemented by yourself. Except for build-in data type, i.e., List in Python. Comment your code. You must write your test code in the main function. Coding style will be evaluated using PEP81. Hints: To easily create a list of search values, half of which are in S and half of which are not when generating the list S, use only even integer values. You can use step=2 in randrange function to control the interval of considered num- bers. For instance odd_rand_num = random.randrange (2,20,2) "https://realpython.com/python-pep8/