Overview

So far in class we’ve talked generally about some things being slow like looking for an item in a list, but we haven’t been very precise about what that means. We want a way to be able to compare between different approaches to solving a problem to see which might be better. Better can mean a lot of things, but today we’re going to focus on how to compare two algorithms based on how fast they will solve the same problem using “Big-O” analysis.

Basic Learning Objectives

Before class, you should be able to:

  • Explain what benchmark analysis is
  • Explain what Big-O notation is and why is is needed over benchmark analysis
  • Define best case and worse case at a high-level

Advanced Learning Objectives

After class, you should be able to:

  • Determine which of the common order of magnitude functions a simple program falls into

Resources

You should read/watch the following and complete the embedded checks: