Programming assignment 1.
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.
- 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 to calculate the worst-case running time when n = 105.
- Calculate how much time your machine takes to run one single line using only your binary search (Hint: look at HW4, what is the time complexity of binary search? How could you use that to calculate the runtime of one line?)
- Now using the previous step, estimate the worst-case running time for each algorithm when n=1015 (You do not need to run any of binary_search or linear_search functions. Just do a simple calculation in your code! Hint: look at HW4).
- Explain part 4 and 5 in words.