Class 20 - Notes

Upcoming Schedule

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.

Slides

Common Costs

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: Θ(N²

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: Θ(2^N)

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?