Computer Science 385
Design and Analysis of Algorithms
Spring 2025, Siena College
Lecture 5: Asymptotic Analysis
Date: Friday, January 31, 2025
Agenda
- Announcements
- Problem Set 1: [PDF] continues
- group formation by today!
- Problem Set 1: [PDF] Q&A
- Lab 1: Counting Operations, Graphs recap
- 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