Asymptotic Analysis

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

• 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.
• Express the formal, mathematical definition of Big-Oh.
• Use the mathematical definition of Big-Oh to prove the asymptotic running time of a given program.
• Express the mathematical definition of Big Omega.
• Use the mathematical definition of Big Omega to prove the 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 the asymptotic running time of a given program.
• Enumerate various asymptotic notations used in this course.
• Elaborate on the benefits of using asymptotic notation and worst-case analysis to study the computational complexity of algorithms.

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