Computer Science 385
Design and Analysis of Algorithms
Spring 2018, Siena College
Lecture 4: Asymptotic Analysis
Date: Friday, January 26, 2018
Agenda
- Announcements
- You may submit Lab 2: Introduction to
METAL Graph Data, until the start
of your next lab meeting
- No coding in lab next week, but you will need your textbook
- Notice: the topic notes on the schedule page
- We'll have a brief quiz on the graph data structure topics
in class on February 5
- Problem Set 1: [HTML] [PDF] out
- 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