Asymptotic Growth Rate

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

• Understand and appreciate why we do asymptotic analysis using Big-Oh notation.
• Use Big-Oh notation to describe asymptotic running time of a program when you are given the program code (or its running time as a function of input size under the RAM model).
• Use Big-Oh notation to describe the asymptotic running time of the operations of the data structures we have implemented so far.
• Understand that Big-Oh (asymptotic) notation groups runtime functions into a set of classes.
• Enumerate common running time functions when the runtime is described in asymptotic (Big-Oh) notation.
• Determine the asymptotic growth rates of a given function using Big-Oh notation.
• Rank asymptotic complexities from smallest to largest.

This chapter does not have a starter/solution code.