Overview

There are many ways to compare programs that solve the same problem, but computer scientists are usually most interested in the speed with which the program can solve the problem. Asymptotic analysis, also called Big-O analysis, is the main way that we analyze the speed of a program. Today we’ll review/dive deeper into this form of analysis.

Basic Learning Objectives

Before class, you should be able to:

  • Explain what worst-case performance is at a high level
  • Identify the Big-O category of a for-loop
  • Explain why asymptotic analysis can be better than benchmark testing

Advanced Learning Objectives

After class, you should be able to:

  • Analyze the worst-case time complexity of more complex programs
  • Demonstrate the underlying mathematical logic of asymptotic analysis

Readings

You should read the reading assignment through Moodle and complete the embedded checks:

  • 2.2-2.4