Computer Science 385
Design and Analysis of Algorithms
Spring 2024, Siena College
Lecture 5: Asymptotic Analysis
Date: Friday, January 26, 2024
Agenda
- Announcements
- Remaining checkoffs for Lab 1: Counting Operations,
Graphs due at the start of your lab on Wednesday
- Problem Set 1: [PDF] is out - see all of the details in the
Canvas assignment
- Asymptotic analysis (some should be review)
- basic complexity ideas
- basic efficiency classes
- Big O,
Big Ω, Big Θ
Terminology
- time vs. space tradeoff
- computational cost
- basic operation
- space cost
- trends
- asymptotic analysis
- Big O
Big Ω, Big Θ
- relative rates of growth
- order of growth/complexity
- constant, logarithmic, linear, quadratic, cubic, polynomial, exponential, factorial
- best/worst/average case complexity
- basic efficiency classes