Computer Science 385

Design and Analysis of Algorithms

Spring 2024, Siena College

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