C
C
CS61B Textbook
Search
⌃K
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))
      .
Previous
13.8 Big-O
Next
13.10 Exercises
Last modified 9mo ago