Day 22: Introduction to Big O Notation

Learning Objectives

• AAP-2.Q: For algorithms: a. Create algorithms. b. Combine and modify existing algorithms.

Essential Questions

• How do computer scientists formally describe algorithm efficiency?
• How does Big O notation help us compare and categorize algorithms?

Materials Needed

• Presentation slides on Big O notation
• Algorithm classification worksheet
• Algorithm efficiency cards
• Graph paper or graphing software
• Exit ticket templates

Vocabulary

• Big O notation
• Time complexity
• O(1) - Constant time
• O(log n) - Logarithmic time
• O(n) - Linear time
• O(n log n) - Linearithmic time
• O(n²) - Quadratic time
• O(2^n) - Exponential time
• Asymptotic analysis

Procedure (50 minutes)

Opening (8 minutes)

1. Review and Connection (3 minutes)

   • Review algorithm efficiency concepts from previous lesson
   • Connect to today's focus on formally classifying algorithm efficiency

2. Warm-up Activity (5 minutes)

   • Show graphs of different growth rates (constant, linear, quadratic, etc.)
   • Ask students to match them to algorithms they've seen
   • Introduce the need for a standardized way to describe these patterns

Main Activities (32 minutes)

3. Lecture: Big O Notation and Common Complexities (12 minutes)

   • Define Big O notation as a way to classify algorithms by their growth rate
   • Explain that Big O describes the worst-case scenario as input size increases
   • Introduce common Big O classifications:
     • O(1) - Constant time: execution time doesn't depend on input size
       • Examples: accessing an array element, simple calculations
     • O(log n) - Logarithmic time: execution time grows logarithmically
       • Examples: binary search
     • O(n) - Linear time: execution time grows proportionally to input size
       • Examples: linear search, simple traversals
     • O(n log n) - Linearithmic time: common for efficient sorting
       • Examples: merge sort, quicksort
     • O(n²) - Quadratic time: execution time grows with square of input size
       • Examples: nested loops, simple sorting algorithms
     • O(2^n) - Exponential time: execution time doubles with each additional input
       • Examples: recursive fibonacci, brute force solutions
   • Explain how to determine Big O for simple algorithms:
     • Count nested loops
     • Identify dominant terms
     • Focus on growth rate, not constants
   • Discuss the difference between efficient and inefficient algorithms
   • Explain why polynomial time algorithms are considered "reasonable"

4. Demo: Determining Big O for Simple Algorithms (8 minutes)

   • Walk through examples of determining Big O complexity:
     • Accessing an element in an array: O(1)
     • Linear search in a list: O(n)
     • Nested loops processing all pairs: O(n²)
     • Binary search in a sorted list: O(log n)
   • Show how to analyze code to determine its complexity
   • Demonstrate how to identify the dominant term
   • Illustrate how different algorithms scale with input size
   • Show graphs of different complexity classes

5. Hands-on: Analyzing Algorithms for Time Complexity (12 minutes)

   • Students work individually or in pairs
   • Provide students with several algorithm implementations
   • Students determine the Big O complexity for each algorithm
   • Students justify their classifications
   • Have students match algorithms to their complexity classes
   • Encourage students to create or modify algorithms to achieve specific complexities

Closing (10 minutes)

6. Activity: Matching Algorithms to Their Big O Classifications (5 minutes)

   • Provide students with a set of algorithm descriptions
   • Students classify each algorithm according to its Big O complexity
   • Discuss the classifications as a class
   • Address any misconceptions or questions
   • Highlight how Big O helps compare algorithms at scale

7. Exit Ticket and Preview (5 minutes)

   • Students determine the Big O complexity of given algorithms
   • Preview that next class will focus on the final project planning and design

Assessment

• Formative: Quality of algorithm classification during hands-on activities
• Exit Ticket: Accuracy of Big O complexity determination

Differentiation

For Advanced Students

• Challenge them with more complex algorithms to analyze
• Introduce more nuanced complexity analysis (best case, average case)
• Have them explore space complexity in addition to time complexity

For Struggling Students

• Focus on the most common complexity classes (O(1), O(n), O(n²))
• Provide more structured analysis templates
• Use visual aids to illustrate different complexity classes

Homework/Extension

• Complete a worksheet on Big O classification
• Research and report on an algorithm with interesting complexity characteristics
• Implement algorithms with different complexity classes and compare their performance

Teacher Notes

• Emphasize that Big O is a simplification that focuses on growth rate
• Watch for confusion about constants and lower-order terms
• Make connections to real-world scenarios where efficiency classifications matter
• Consider using animations or visualizations to show growth rates
• Remind students that while formal Big O analysis is beyond AP CSP, understanding efficiency classifications is important