| date | duration | maintainer | order | title |
|---|---|---|---|---|
w3d2 |
50 |
artificialsoph |
2 |
Complexity Intro |
- (30 m) Complexity Slides
- (20 m) Complexity in practice notebook
Students should be able to:
- Explain the value of complexity analysis and how it would be applied to projects in theory.
- Apply complexity analysis to their existing and futoure work.
- Meaure the wall clock time of real code.
- Programmatically measure wall clock time of real code.
- Use a line profiler to check and inform big-O complexity analysis.
- Use the heuristic method to find Big-O complexity
Very important Before starting this, update the notebook to use solutions that students have submitted for pair problems so far. I've included two pairs often taught in the first week (Reverse String and Can You Spell) but you may be teaching something different. If so, update the solutions in the notebook.
This lecture teaches a heuristic method for finding the big-O complexity of an alorithm. At the end of the slide deck is an optional component with an example of using a proof.
- Lecture Notes - USF CS
- Cracking the Coding Interview has many examples with solutions & explanations
- Rob Bell's Guide to Big O Notation
- High level, assumes familiarity already
- Touches on space complexity
- Good review questions
Chad's lecture notes
- Dives in w/ examples
- Better academic coverage
- Tradeoff between maintainability and complexity
USF CS 245 lecture notes
- From David Galles
- Touches on benchmarking algorithms
- Wall clock vs mathemtatical model
- Touches on space / time trade off
- Discussion of best, worst and average
- Comparison of linear vs binary search
- Big O
- Leading terms, dropping constants
- General guidelines
- A handful of examples
Rob Bell's blog
- Describes each common complexity