Computer Science 210
Data Structures
Fall 2019, Siena College
Lecture 11: Big O Complexity; Generic Classes; Introduction to Recursion
Date: Friday, September 27, 2019
Agenda
- Announcements
- zyBook Assignment 3, due October 3
- Problem Set 2: not due until after the exam, but it's good practice!
- Evening exam next Tuesday, 7-9 PM
- review times on Monday, September 30: with me 4-5 PM in RB
250, 6-7 PM with Prof. White in RB 304
- Complexity and asymptotic analysis
- Generic classes
- Introduction to Recursive Methods
Terminology
- computational cost
- basic operation
- space cost
- trends
- asymptotic analysis
- Big O
- relative rates of growth
- order of growth/complexity
- constant, logarithmic, linear, quadratic, cubic, polynomial, exponential, factorial
- best/worst/average case complexity
Examples