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
- In Class Discussion
- Videos from the Online Class