Preferably in Java with comments.

Implement linearSearch(a,key) and binarySearch(a,key) functions.

Part B. In this part we will calculate the worst-case running time of each function.

1. Request the user to enter a positive integer, and call it n. (n = 105)

2. Generate n random integers between -1000 to 1000 and save them in array a.

3. Sort a (you can use any sorting algorithm you want.

4. Now to have the worst-case scenario, set the value of the key to 5000 to make sure it does not exist

   in the array.

5. Run each function ONLY once to calculate the worst-case running time when n = 105.

6. Calculate how much time your machine takes to run one single step using your binary search

   function. (Hint: look at HW4)

7. Now using the previous step, write a code to calculate the worst-case running time for each

   algorithm when n=107 (You do not use a timer for this step. Just a simple calculation!).