Let us analyze the runtime complexity of two algorithms, i.e., linear search (Algorithm A) and binary search (Algorithm B) using the experimental method.

Algorithm A: Store the list S in an array or list, in whatever order the values are given. Search the list from beginning to end. If S[i] == x 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 worse 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.If we are doing a very small number of searches, Algorithm A is preferableHowever 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 oset 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

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 S in an array or list, in whatever order the values

are given. Search the list from beginning to end. If S[i] == x 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 worse 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.

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 oset 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 function. You may use any sorting of 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 seperately to search the k target values in S.

- Design and conduct experiements 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 k.

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 numbers. For instance odd_rand_num = random.randrange(2,20,2)

will return any random number between 2 to 20, such as 2, 4, 6, . . . 18. It will never select 20.

randomly choose some elements of S as the first half of the search list

randomly choose odd integer values as the second half of the search list

PLEASE use python as progmmaring language