Comment on page

# 13.9 Summary

To summarize this chapter:

- Given a piece of code, we can express its runtime as a function$R(N)$
- $N$is a
**property**of the input of the function often representing the**size**of the input

- Rather than finding the exact value of$R(N)$, we only worry about finding the
**order of growth**of$R(N)$. - One approach (not universal):
- Choose a representative operation
- Let$C(N)$be the count of how many times that operation occurs as a function of$N$.
- Determine order of growth$f(N)$for$C(N)$, i.e.$C(N)\in \Theta(f(N))$
- Often (but not always) we consider the worst case count.
- If operation takes constant time, then$R(N)\in \Theta(f(N))$.

Last modified 9mo ago