Implement * linearSearch(a,key)* and

*functions.*

__binarySearch(a,key)____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 = 10__^{5} - Generate
**n**random integers betweento__-1000____1000__**a**. - Sort
**a**(you can use any sorting algorithm you want.*)* - 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**100**

(**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
__ONLY__*once***worst-case running time**when**n = 10**.^{5} - Calculate how much time your machine takes to run
**one**single step using your binary search function. (: look at HW4)__Hint__ - Now using the
**previous**step,**write a code**to calculate the worst-case running time for each algorithm when**n=10**^{7 }(**You do not use a timer for this step. Just a simple calculation!)**.

## Reviews

There are no reviews yet.