Outline:

1. Questions?
2. Counting steps
   • exact counting
   • as a function
   • practice: Exercises 1+2
3. Big-O
   • basics and intuition
   • more formally
4. Wrap-up

What’s next

• Quiz 2 will be next Monday and cover the following Quiz Learning Objectives:
  • OO 1: objects
  • OO 2: interfaces
  • OO 3: inheritance
  • TC 1: complexity classes
  • [if space] KF 1: variables
• Assignment 2 is due next Wednesday

What you should do now:

• The readings (see below)
• Complete Question 1 of Assignment 2 today
• Practice with classes, inheritance, and interface (Lab 2 may help)

Reading assignment (to be completed by the next class):

Big-O notation (from today):

• Big-O Notation

Want more on Big-O and expressions like it? See these:

• Types of Asymptotic Notation
• Properties of Asymptotic Notation

Stacks (for next time):

• Stack Data Structure