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 (precise) running time as a function of input size.
• 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 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.