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