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

Last updated