Class 20 - Notes
If you feel like you didn’t understand how to describe computing cost to answer Problem 5 and Problem 10 well, but do after class today, you can submit an addendum to your Project 4 by 6:59pm tomorrow (Thursday), and still be eligible for Blue Best Test on Monday.
To be eligible to take the Blue Belt test on Monday, 21 March, you must have (1) completed the Green Belt, and (2) submitted a satisfactory Project 4. (If you are not eligible to take the first Blue Belt test opportunity, you will have more opportunities for Blue Belt promotion later.) See Notes 19 for details on the Blue Belt test.
Constant Time: O(1)
Execution time does not grow with size of input
Either size of input is fixed, or the code does not even need to look at all of the input
What are examples of functions with constant running time?
Linear Time: Θ(N)
Execution time grows linearly with size of input
Increasing the size of the input by one unit, increases the work by a constant amount.
What are examples of functions with linear running time?
Quadratic Time: Θ(N2
Execution time grows as square of size of input
Increasing the size of the input by one unit, adds work that is the size of the input.
What are examples of functions with quadratic running time?
Exponential Time: Θ(2N)
Grows exponentially in size of input
Increasing the size of the input by one unit, doubles the amount of work.
What are examples of functions with exponential running time?