Lab 7: Big-O Runtime Analysis
Due Date and Submission Requirements
- Due Date: Tuesday, March 19th 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 n is part of your running time, make sure you mention 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 7 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