AP CSP Day 22 - Introduction to Big O Notation

Course Information

• Course: AP Computer Science Principles
• Unit: Big Idea 1 - Creative Development (CRD)
• Lesson: Day 22 (50 minutes)
• Learning Objective: CRD-1.V - Use Big O notation appropriately

Learning Objectives

Primary Goals

Students will be able to:

1. Understand the concept of Big O notation
2. Use Big O notation to describe algorithm efficiency
3. Test and refine program logic involving Big O notation
4. Analyze real-world scenarios that require Big O notation

AP Exam Alignment

• Big Idea 1: Creative Development (10-13% of AP Exam)
• Essential Knowledge: CRD-1.V.1, CRD-1.V.2, CRD-1.V.3
• Computational Thinking Practice: 1.A - Investigate the situation, context, or task

Lesson Structure (50 minutes)

Opening Hook (10 minutes)

1.1 Welcome & Lesson Preview (5 minutes)

Teacher Activities:

• Recap previous day's content on algorithm efficiency
• Introduce today's topic on Big O notation

Student Activities:

• Think about: "What are some examples where we use Big O notation in daily life?"

1.2 Big O Notation Examples Challenge (5 minutes)

Activity: "Identify the Big O Notation"
Instructions:

• Groups of 4-6 students
• Identify Big O notations in given scenarios
• Discuss the importance of Big O notation

Purpose: Activate thinking about Big O notation

Core Content Instruction (20 minutes)

2.1 What is Big O Notation? (10 minutes)

Definition (CRD-1.V.1):

Big O notation describes the performance or complexity of an algorithm.

Key Concepts:

• O(1): Constant time
• O(n): Linear time
• O(n^2): Quadratic time
• O(log n): Logarithmic time

Case Study: Using Big O notation in a simple program

• Program: Compare linear search O(n) vs. binary search O(log n)
• Notation structure: Linear search O(n), Binary search O(log n)

2.2 Common Big O Notation Metrics (5 minutes)

Examples:

• Constant time: Accessing an array element by index
• Linear time: Traversing a list
• Quadratic time: Nested loops
• Logarithmic time: Binary search

Discussion Questions:

1. What makes good Big O notation usage?
2. Can you think of an example where Big O notation is used in daily life?
3. Why is Big O notation important in programming?

2.3 Advanced Big O Notation Concepts (5 minutes)

Why is it important?:

• Scalability: Handling larger datasets
• Optimization: Improving performance

Discussion Questions:

1. How can we optimize algorithms using Big O notation?
2. Why is scalability important when using Big O notation?

Hands-On Activity (15 minutes)

3.1 Group Project: Evaluate Algorithms with Big O Notation (15 minutes)

Activity: "Design a Program"
Instructions:

• Groups of 3-4 students
• Design a program that evaluates algorithms using Big O notation
• Test the program for correctness
• Present the program to the class

Materials:

• **Program design worksheet
• **Big O notation checklist

Learning Goals:

• **Understand Big O notation
• **Use Big O notation to describe algorithm efficiency
• **Test program logic involving Big O notation
• **Present ideas effectively

Assessment:

• **Group participation
• **Program quality
• **Testing thoroughness
• **Presentation clarity

Closure & Preview (5 minutes)

4.1 Key Concepts Review (2 minutes)

Today's Learning Highlights:

1. ✅ Understanding the concept of Big O notation
2. ✅ Using Big O notation to describe algorithm efficiency
3. ✅ Testing and refining program logic involving Big O notation
4. ✅ Analyzing real-world scenarios that require Big O notation

AP Exam Connection:

• These concepts will appear in AP exam multiple choice questions
• Understanding Big O notation is crucial for the Create Performance Task

4.2 Next Class Preview (3 minutes)

Day 23 Topic: "Final Project - Planning and Design"

• Learning Objective: CRD-1.W - Plan and design a final project
• Activity: Practicing project planning
• Homework: Think about a recent program you used. What Big O notation did it employ?