CSSE 473: Session Notes - Day 2

Topics

1. The analysis framework
2. Asymptotic notations and basic efficiency classes
3. Analysis of iterative algorithms

Outline

1. [3 min] Time/space complexity: Merge vs Quicksort
2. [2 min] Measuring an input’s size: data structures vs gcd
3. [2 min] Units of measuring running time: count the important stuff
4. [3 min] Basic efficiency classes
5. [5 min] Worst/best/avg cases complexities and when/who might be interested in them. And no, the best case does not happen when the input size is zero.
6. [10 min] Big-Oh/Omega/Theta notations
7. [5 min] Use of limits with examples/worksheet
8. [20 min] Practice of analysis of non-recursive algorithms

Resources

• slides
• worksheet

Homework

1. Day 3, BC: Sections 2.4-2.5