Lesson 3: Introduction to Asymptotic Complexity
We've learned a bunch of C++, and we're ready to start using our C++ knowledge to build data structures!
As we learn about different structures in the second half of the course, we'll want a formal way to compare their performance.
-
Today, we'll look at some of the ways we can think about how long it takes to perform an operation.
This lesson addresses aspects of the following course learning goals in Group 7:
- Goal 7A: Measuring Cost:
- Explain the benefits and limitations of empirical testing, counting operations, and asymptotic analysis as ways to measure cost.
- Goal 7B: Asymptotic Complexity:
- Compare and contrast \( \mathrm{o}() \), \( \mathrm{O}() \), \( \Theta() \), \( \Omega() \), and \( \omega() \), including identifying which to use to describe specific operations.
- Goal 7C: Complexity Analyses:
- Explain the difference between the following analyses:
- Best case
- Expected case
- Worst case
- Perform these analyses on uncomplicated algorithms.
- Explain the difference between the following analyses:
Outline
Was all that math tiring? Consider taking a break!
You might want to grab a stretch before we move on to the next topic.
- Asymptotic Complexity Analysis
- Big \( \Theta{} \)
- \( \Theta{} \) Abstracts Away Coefficients
- \( \Theta{} \) Abstracts Away the Choice of Operation
- \( \Theta{} \) Abstracts Away the Choice of \( n \) (mostly)
There's not a ton left, but if you are feeling fatigued, you could take a breather here.
- Case Study: Linear Search
- \( \mathrm{O} \) and \( \Omega \)
- The Whole Asymptotic Family
- Key Points
- Before You Go
To receive credit: complete all pages above, then this page will be complete as well (and get a green check emoji at the bottom right of the page).
(When logged in, completion status appears here.)