1. LxD Cycle Process

Empathize: Students judge efficiency by how long the code looks rather than how many times it runs, so they cannot compare two versions that produce the same output.

Define:

  • POV: CSA students need to count executions from the header, because the AP exam asks for statement counts and comparisons rather than timings.
  • Learning Goal: Students will compute execution counts from loop headers, multiply counts for nested loops, and compare two versions producing the same output.

Ideate:

  • HMW Question: How might we let students prove a work comparison with a counter, instead of guessing from how the code looks?
  • Activity: A step loop counting activity, a same-output-less-work comparison, and a reason-about-counts exercise.

Prototype & Test: Every activity keeps a visible counter, so a predicted count is checked against a measured one rather than accepted.

2. Lesson Plan

Learning Objective: Compute statement execution counts and informal run-time comparison of iterative statements.

Success Criteria: You can count how many times a statement runs from the loop header alone, multiply counts for nested loops, and say which of two versions does less work.

Tech Talk & Introduction (5 minutes)

Informal run-time analysis means counting statement executions, not timing the program.

  • A loop that runs n times executes each statement in its body n times.
  • Nested loops multiply: an outer loop of m around an inner loop of n runs the inner body m * n times.
  • A loop whose variable changes by a step larger than 1 runs fewer times. Stepping by k up to n runs about n / k times.
  • Two versions can print identical output and do very different amounts of work.

3. Reference Guide

Key Ideas

  • A statement execution count is the number of times one statement runs while the program runs.
  • Count from the header, not by tracing every pass:
    • for (int i = a; i < b; i++) runs b - a times (when b > a).
    • for (int i = a; i <= b; i++) runs b - a + 1 times.
    • Stepping by s: count the values a, a + s, a + 2s, ... that satisfy the condition.
  • Nested loops multiply: an inner statement runs outer count * inner count times.
  • A statement inside an if runs only on the passes where the condition is true.
  • Fewer executions usually means a faster program. Compare two versions by counting.

Quick Reference

Loop header Values of the variable Count
i = 0; i < 10; i++ 0 to 9 10
i = 1; i <= 10; i++ 1 to 10 10
i = 5; i < 10; i++ 5 to 9 5
i = 0; i < 10; i += 3 0, 3, 6, 9 4
i = 10; i > 0; i -= 2 10, 8, 6, 4, 2 5

4. Code Examples

A. Simple: Counting in Code

This program counts its own statement executions. Run it, then change the loop bounds and predict the new counts before running again.

Code Runner Challenge

Count executions with counters. Change the bounds and predict before running.

View IPYNB Source 
// CODE_RUNNER: Count executions with counters. Change the bounds and predict before running.
public class ExecutionCounts {
    public static void main(String[] args) {
        int checks = 0;
        int hits = 0;
        for (int k = 0; k < 30; k++) {
            checks++;                 // counts the if check
            if (k % 3 == 0) {
                hits++;               // counts the body of the if
            }
        }
        System.out.println("if checked: " + checks + " times, body ran: " + hits + " times");

        int innerRuns = 0;
        for (int outer = 0; outer < 3; outer++) {
            for (int inner = 0; inner < 4; inner++) {
                innerRuns++;
            }
        }
        System.out.println("inner statement ran: " + innerRuns + " times");
    }
}
ExecutionCounts.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

5. Hacks & Practice Tasks

Prepare your submission IPYNB

  1. Create a new notebook in your portfolio homework area: _notebooks/homework.
  2. Add one markdown cell at the top with the frontmatter:
---
layout: post
title: CSA Unit 2.12 Informal Run-Time Analysis HW
categories: [Java, Run-Time-Analysis]
lesson_language: Java
lesson_topic: Run-Time-Analysis HW
lesson_source: APCSA
lesson_type: lesson
permalink: /csa/unit_02/2_12_hw
author: yourGithubID
---
  1. Add code cells for the Popcorn Hack and the Homework Hack. Ensure all code runs and output is visible.
  2. Include a markdown cell before each code section explaining the concept.

Submission Safety Rules (Read First)

[IMPORTANT] To avoid grading errors, follow these rules exactly:

  • Write your prediction before you run each code section
  • Execute every code cell and leave the output visible
  • Show your work for any hand-traced prediction
  • Do not just copy code; explain what each line does
  • Label each question clearly

Activity 1: Count Two Statements

The if runs on every pass. The count++ runs only when the condition is true.

Statement Execution Counts
Type a number for each statement.
Question 1

How many times does statement 1 (the if check) execute?

int count = 0;
for (int k = 0; k < 30; k++) {
if (k % 3 == 0) { // statement 1
count++; // statement 2
}
}
Question 2

How many times does statement 2 (count++) execute?

Activity 2: Step Loops

Stepping by 3
Predict, then count.
Nested Loops Multiply
Predict, then count.

Activity 3: Same Output, Less Work

Both loops print the multiples of 5 below n. Move the slider and compare how many times each loop’s body runs.

Compare Two Versions
Version B skips the values that never print.

Activity 4: Reason About Counts

Run-Time Questions
Three questions in the style of the AP exam.
Question 1

What are the minimum and maximum number of times statement 4 executes?

int num = (int)(Math.random() * 10);
while (num % 2 != 0) {
num = (int)(Math.random() * 10); // statement 4
}
Question 2

How many times does sum += i * j execute?

for (int i = 1; i <= 10; i++) {
for (int j = i; j <= 10; j++) {
sum += i * j;
}
}
Question 3

Which loop executes its println the fewest times?

Popcorn Hack (In-Class)

Rewrite the loop so it prints exactly the same numbers with far fewer passes. Keep the counter so you can prove it: the original does 135 passes.

Code Runner Challenge

Popcorn hack: same output, 27 passes instead of 135.

View IPYNB Source 
// CODE_RUNNER: Popcorn hack: same output, 27 passes instead of 135.
public class FasterLoop {
    public static void main(String[] args) {
        int passes = 0;

        // TODO: rewrite this loop so it does 27 passes instead of 135
        for (int k = 0; k < 135; k++) {
            passes++;
            if (k % 5 == 0) {
                System.out.print(k + " ");
            }
        }

        System.out.println();
        System.out.println("Passes: " + passes);   // goal: 27
    }
}
FasterLoop.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Homework Hack

Two short tasks.

  1. Finish the runner: predict the three counts in the comments, then add counters to check yourself.
  2. Answer the quick check.

Code Runner Challenge

Homework: predict each count, then verify with counters. Answers: 4, 6, 3.

View IPYNB Source 
// CODE_RUNNER: Homework: predict each count, then verify with counters. Answers: 4, 6, 3.
public class PredictCounts {
    public static void main(String[] args) {
        // Loop 1: how many times does the println run? Prediction: ____
        for (int i = 3; i <= 18; i += 5) {
            System.out.println("Loop 1: " + i);
        }

        // Loop 2: how many times does the println run? Prediction: ____
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < i; j++) {
                System.out.println("Loop 2: " + i + "," + j);
            }
        }

        // Loop 3: how many times does the println run? Prediction: ____
        int n = 64;
        while (n > 1) {
            n = n / 4;
            System.out.println("Loop 3: " + n);
        }

        // TODO: add int counters that count each println and print them at the end
    }
}
PredictCounts.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...
Homework Quick Check
Type a number.

How many times does System.out.println(i + j) execute?

for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j += 3) {
System.out.println(i + j);
}
}

6. Grading Plan (1 Point Total)

Classroom Rubric

  • 0.2 points: Popcorn completion Student rewrote the loop to print the same numbers in far fewer passes and used the counter to prove it against the original 135 passes.

  • 0.8 points: Homework completion

    • 0.5 Three counts: The three execution counts in the runner comments are predicted first, then verified with counters.
    • 0.2 Quick check: The comparison question is answered with the counts that justify it.
    • 0.1 Notebook quality: Every code cell executed with output visible, and a markdown cell before each code section explaining the concept.

Quick Validation Checklist

  • Present: prediction written before the counters were added
  • Present: counters that report the actual number of passes
  • Absent: a claim about which version is faster with no count to support it
  • Test: the rewritten Popcorn loop prints identical output with fewer passes

7. Lesson Revisions & Feedback Evidence

Feedback Received: Team review of the Unit 2 set found that these lessons did not follow the section format used by the Unit 1 lessons, and that they ended without the assignment submission form every other CSA lesson provides.

Revision Made: The lesson was reorganised into the shared CSA lesson format, so it now opens with the LxD cycle and lesson plan, states its reference material before the code, and groups the activities, Popcorn Hack and Homework Hack under one practice section. The duplicate lesson heading was removed, and the page now renders the standard Submit Assignment form at the end.

Design Decision Kept: Every activity keeps a visible counter, so a predicted count is checked against a measured one rather than accepted.

Open Item: Record peer feedback from the team teach delivery here once the lesson has been taught.

8. Summary

  • Count executions from the loop header: list the values the variable takes.
  • Nested loops multiply; if statements filter.
  • Random conditions can have a minimum of 0 and no maximum.
  • Compare versions by counting; skipping unnecessary passes makes code faster.
  • You are ready for the Unit 2 quiz.

9. References

College Board Course and Exam Description

Topic 2.12, Informal Run-Time Analysis, is required content on the AP Computer Science A Exam. The objective quoted in section 2 of this lesson is the College Board’s own wording for this topic, and the activities, Popcorn Hack and Homework Hack are all written against it.

Outside Academic Reference

Counting statement executions is the informal form of the standard analysis of iterative algorithms, where cost is expressed as a count of elementary operations rather than elapsed time.

Reference List

College Board. (2025). AP Computer Science A: Course and exam description. https://apcentral.collegeboard.org/courses/ap-computer-science-a

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press.

Submit Assignment

Click to upload or drag and drop
PDF, ZIP, images, documents, or Jupyter notebooks (.ipynb) (Max 10MB per file)

Need to update a submission later? Open the submissions dashboard.