Computer Science 210
Data Structures
Fall 2017, Siena College
Lecture 12: Complexity and Asymptotic Analysis; Introduction to Recursive Methods
Date: Monday, Octomber 2, 2017
Agenda
- Announcements
- reminder about lecture assignment grading criteria: full
credit awarded does not necessarily mean completely correct
responses
- Lab 3: ArrayList Practice due Wednesday morning
- Programming Project 2: Working with Highway Data, due a
week from today.
- Exam 1 during labs Wednesday
- sample exam solutions are posted outside my door
- review session, Tuesday 10/3, 7:30-8:30 in RB 302
- 10% or 15% of course grade, depending on scores on
subsequent exams
- Considering the costs of some Vector/ArrayList methods
- Complexity and asymptotic analysis
Lecture 12 Assignment
Due at the start of class, Friday, October 6.
Please submit answers to these questions in
Blackboard under "Lecture 12 Assignment" by the start of
class. We will discuss these questions at the start of class, so no
late submissions can be accepted.
- Bailey Problem 5.2, p. 112. See the implementation of
this method in the Vector class in structure5. (4 points)
- Bailey Problem 5.5, p. 112. (3 points)
Terminology
- time vs. space tradeoff
- 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