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)R(N)
    • NN
      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)R(N)
    , we only worry about finding the order of growth of
    R(N)R(N)
    .
  • One approach (not universal):
    • Choose a representative operation
    • Let
      C(N)C(N)
      be the count of how many times that operation occurs as a function of
      NN
      .
    • Determine order of growth
      f(N)f(N)
      for
      C(N)C(N)
      , i.e.
      C(N)Θ(f(N))C(N)\in \Theta(f(N))
    • Often (but not always) we consider the worst case count.
    • If operation takes constant time, then
      R(N)Θ(f(N))R(N)\in \Theta(f(N))
      .