Lab 3, CSC 202
For this lab, you will take some simple measurements of running time, for a few of the functions we have discussed in class.
Develop the range function, that accepts an integer and returns a linked list of the numbers from 0 up to n-1.
Develop the occurs function, that accepts an integer and a list and returns true exactly when the number appears in the list.
Develop the has_dup function, that accepts a list of numbers and returns true exactly when it contains one or more duplicates.
Using the insert function you developed earlier, develop the insertion-sort function that sorts elements by inserting them into the result of the recursive call.
Using the time.perf_counter() built-in function in Python, test the time taken by the range function. Draw a graph of the results. Your graph should include at least ten different values. Each point on the graph should be obtained as the result of averaging four different calls to the function with the given argument.
Do the same for occurs. In this case, do your tests on the worst case. Think about what the worst case for occurs is.
Do the same for has_dup. Again, do a worst-case analysis.
Do the same for insert. Again, do a worst-case analysis.
Do the same for insertion-sort. Again, do a worst-case analysis. Again, think about what the worst case for insertion sort is.
Finaly, combine all of your graphs into a single lab report. The lab report should separate each section clearly, include the code and the graph and your thinking about the worst case, and draw a conclusion about the running-time category of the function.
Add this lab report to your repository as a PDF.