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))$.