Asymptotic Analysis

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

  • Express the formal, mathematical definition of Big Oh.
  • Use the mathematical definition of Big Oh to prove asymptotic running time of a given program.
  • Express the mathematical definition of Big Omega.
  • Use the mathematical definition of Big Omega to prove asymptotic running time of a given program.
  • Recognize that big Oh and big Omega are not necessarily tight bounds.
  • Recognize growth rate type (upper or lower bound) is different from worst case vs. best case analysis.
  • Express the mathematical definition of Big Theta.
  • Use the definition of Big Theta to show asymptotic running time of a given program.
  • Enumerate various asymptotic notation used in this course.
  • Explain what is meant by asymptotic complexity analysis of an algorithm.
  • Contrast between time vs space complexity.
  • Express the space requirements for a given code segment as a function of the input size in the worst case scenario.
  • Elaborate on the benefits of using asymptotic notation and worst-case analysis to study computational complexity of algorithms.

This topic will be the most mathematically demanding part of this course. However, once you understand the intuition behind the formalism, it becomes a lot easier to deal with.