Lab 9: Spooky Big-O Runtime Analysis
Due Date and Submission Requirements
- Due Date: Thursday, October 31st at 11:59 p.m.
- Partner Information: This is an individual assignment. You are allowed to collaborate with other students, but each student must submit their individual, independent solution.
- Submission Instructions: You will not be submitting any code for this assignment. You will submit your solution as a pdf to the appropriate D2L dropbox.
The goal of this lab is:
- Gain experience analyzing the running time of different algorithms
- Use Big-O notation to describe the running time of an algorithm
Directions
You will determine the running time of four different algorithms in this lab. For each operation/line of code in the algorithm, you must find the time complexity/running time of that operation (just like we did in class and on the midterm exam). Then you must state the
total running time of the algorithm using Big O notation. In your final answer, you should drop all non-dominant factors and multiplicative factors. If you say something is O(n) or O(n^2), make sure you state what n is
You can print out the lab instructions below and fill our your solution by hand and scan it as a pdf, or you can fill it out digitally (pdf editor, word, document editor) and submit it as a pdf.
Lab 9 Algorithms
Grading (10 points)
- 3 points- The running time analysis for algorithm 1 is correct
- 3 points- The running time analysis for algorithm 2 is correct
- 2 points- The running time analysis for algorithm 3 is correct
- 2 points- The running time analysis for algorithm 4 is correct
Deductions
-100000000 if you don't submit your lab as a pdf file