Week 3: Algorithm Analysis
Outcomes
You should be able to:
- Explain the idea of Big-Oh (Omega) notation.
- Recognize the name and symbol for each common function type discussed in Big-Oh notation.
-
| function |
name |
| O(1) |
constant |
| O(log n) |
logarithmic |
| O(n) |
linear |
| O(n log n) |
log linear |
| O(n2) |
quadratic |
| O(n3) |
cubic |
| O(2n) |
exponential |
| O(n!) |
factorial |
- Given two or more Big-Oh notation/function types (as above) put them in order from slowest growth to fastest growth.
- Given an algorithm, compute it Big-Oh notation. [This week we focus only on O(1), O(n), and O(n2)]
- Given an algorithm, write an accurate 2-3 sentence description of what it will do.
Activities
- Reading Assignment
- Notes
- Section 2.2
- Section 2.3
- Very important
- In particular start to pay attention to Table 1 and the material/vocabulary represented there.
- Section 2.4
- Interesting examples that start to illustrate the Big-Oh introduced in the previous section
- Videos
- Schafer's take on Big-Oh notation
- YTI #3
- Consider the 12 functions provided in the following file.
- For each:
- What is the Big-Oh value (O(1), O(n) or O(n2)
- In 1 or 2 sentences, what does this function do?
- It seems more mathy than it is. Don't overthink it.
- ONLY, after you are done with the above activity should you
- Compare your answers to my key [Document]
- Walkthrough video where I explain the answer key [Video, 60 minutes]
- Note, this video comes in at 60 minutes which is kind of long.
- BUT, it is my guess that if this activity gave you troubles it may only be one or two, not the entire set of 12. So you can skip to the explanation for where you had trouble.
- And if the whole thing was still giving you issues, this will hopefully help you out.
- If you still have questions PLEASE reach out to me. I want this to make sense as we move forward.
Additional Resources
- You may have noticed this on the table of contents page for your textbook. Professor Gerry Jenkins is a retired professor from Long Beach City College who made a bunch of videos to correspond with the readings in your textbook. I have NOT viewed all of them. But, I know how helpful it can be to have a wide variety of study resources.
After reading section 2.4