I need help with my algorithm assignment please! we can use any language we want. I prefer to work with Java.

Implement linearSearch(a,key) and binarySearch(a,key) functions. Part A. In this part we will calculate the average-case running time of each function.

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

Generate n random integers between -1000 to 1000 and save them in array a. (You can use randi

function in MATLAB)

Sort a (you can use any sorting algorithm you want. If you are using MATLAB, you can call the sort

function to sort your numbers)

Pick a random number in a and save it in variable called key.

Call each function separately to search for the key in the given array.

To calculate the average-running time, you need to have a timer to save the total runtime when

repeating step 4 and 5 for 500 times. (tic toc in MATLAB)

(Note1: Do not forget to divide the runtime by the number of the times you run step 4-5)

(Note2: Remember to choose a different random number each time you go back to step 4.) Part B. In this part we will calculate the worst-case running time of each function.

Repeat steps 1 to 3 in part A.

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.

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

Calculate how much time your machine takes to run one single step.

Now estimate the worst-case running time for each algorithm when n=107.

Now repeat step 1-3 for n = 107 and compare the actual running time with your answer in step 5.