Computer Science 385
Design and Analysis of Algorithms
Spring 2019, Siena College
Lecture 5: Asymptotic Analysis
Date: Friday, January 25, 2019
Agenda
- Announcements
- Today at 12:30 in RB 202: talk by Dr. Bellis (and maybe
others) about entrepreneurial opportunities at Siena
- 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
- A few words and hints about wrapping up
Lab 2: Introduction to METAL Graph Data
- Problem Set 1: [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