# 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*^{2}

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?