Lesson 2.12: Informal Run-Time Analysis
Lesson 2.12: Informal Run-Time Analysis
What You'll Learn
- 2.12.A: Calculate statement execution counts and compare iterative statements. (EK 2.12.A.1)
- Count how many times a statement executes in a single loop.
- Count how many times a statement executes in nested loops.
- Determine how execution count changes when n doubles (linear vs. quadratic).
- Compare execution efficiency of two algorithm implementations.
Key Vocabulary
| Term | Definition |
|---|---|
| statement execution count | The number of times a specific statement is executed by a program. Calculated by tracing or algebraic analysis of loop bounds. (EK 2.12.A.1) |
| informal run-time analysis | Estimating how execution count grows as input size increases, without formal Big-O notation. Focuses on counting loop iterations. (EK 2.12.A.1) |
| linear growth | When the execution count grows proportionally to the input size n. A single loop from 1 to n has linear growth. |
| quadratic growth | When execution count grows proportionally to n². A nested loop where both bounds are n has quadratic growth. |
| loop bound analysis | Determining the exact number of times a loop body executes by analyzing the initialization, condition, and update. |
Statement Execution Counts (EK 2.12.A.1)
A statement execution count tells you exactly how many times a specific line of code runs during program execution. The CED states that these "are often calculated informally through tracing and analysis of the iterative statements." The AP exam tests this directly — you will be asked to determine how many times a statement executes given specific values, or how the count changes when loop bounds change.
CED Connection (EK 2.12.A.1)
"A statement execution count indicates the number of times a statement is executed by the program. Statement execution counts are often calculated informally through tracing and analysis of the iterative statements."
Counting Single Loop Executions
For a simple for loop, the execution count of the body equals the number of times the condition is true. The formula: when i goes from start to end with step 1, the count is end - start + 1 for <=, or end - start for <.
Worked Example — Single Loop Counts
// How many times does line A execute?
for (int i = 1; i <= 10; i++) {
System.out.println(i); // line A
}
// i goes 1,2,...,10 → 10 times
for (int i = 0; i < 10; i++) {
System.out.println(i); // line B
}
// i goes 0,1,...,9 → 10 times (same!)
for (int i = 1; i <= n; i++) {
System.out.println(i); // line C
}
// Executes n times (linear in n)
for (int i = 0; i < n; i += 2) {
System.out.println(i); // line D
}
// i goes 0,2,4,... → approximately n/2 times
Counting Nested Loop Executions
For nested loops, multiply when bounds are independent, sum when the inner bound depends on the outer variable. This directly extends the Topic 2.11 analysis.
Worked Example — Nested Loop Counts
// How many times does line A execute?
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 3; j++) {
System.out.println(i + j); // line A: 4 * 3 = 12 times
}
}
// Inner bound depends on outer:
for (int i = 1; i <= 5; i++) {
for (int j = 1; j <= i; j++) {
System.out.println(j); // line B
}
}
// i=1: 1 time | i=2: 2 | i=3: 3 | i=4: 4 | i=5: 5
// Total: 1+2+3+4+5 = 15 times
// General: 1+2+...+n = n*(n+1)/2 ≈ n²/2 (quadratic)
Comparing Algorithm Efficiency
Two algorithms that solve the same problem may have very different execution counts as input size grows. The AP exam asks you to identify which of two loops executes more times, or by how much the count changes when n doubles.
Worked Example — Comparing Two Approaches
// Algorithm A: single loop
for (int i = 0; i < n; i++) {
process(i); // executes n times
}
// Algorithm B: nested loop (for the same task, badly written)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) process(i); // executes n² times, but process() only n
}
}
// Algorithm A is far more efficient for large n.
// When n=100: A runs 100 times, B runs 10,000 times.
This is the core insight of run-time analysis: as n grows, the difference between linear (n) and quadratic (n²) execution counts becomes enormous. For n=1,000,000, linear runs 1 million times; quadratic runs 1 trillion times.
Worked Example — How Count Changes When n Doubles
// Linear: count = n
// If n doubles from 50 to 100: count doubles (50 → 100)
// Quadratic: count = n²
// If n doubles from 50 to 100: count quadruples (2500 → 10000)
// Determine which is faster by substituting values:
int n = 100;
// Loop A: count = n
for (int i = 0; i < n; i++) { /* 100 times */ }
// Loop B: count = n*(n+1)/2
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) { /* 5050 times */ }
}
AP Trap: Confusing Loop Bound Types
i < n gives n iterations; i <= n gives n+1 iterations. On execution count questions, always check the condition carefully before computing. Off by one here means off by n in nested loops.
AP Trap: Counting When Condition Has selection Inside
When an if inside a loop gates which iterations do work, the loop body statement count depends on the data. The question "how many times does the loop execute?" (always) differs from "how many times does the if-body execute?" (depends on input). AP exam questions are precise about which statement they are asking about.
Real-World Connection
Run-time analysis is how engineers decide which algorithm to use in production. Sorting a list of 1,000 items with a quadratic algorithm takes 1,000,000 operations; a linear algorithm takes 1,000. For a streaming service with 200 million users, choosing an O(n) algorithm over O(n²) is the difference between a system that responds instantly and one that would take years to complete a single request. This topic is the gateway to formal algorithmic complexity analysis in future CS courses.
Summary
- Execution count = number of times a statement runs. Calculate by tracing or algebra. (EK 2.12.A.1)
- Single loop from 0 to n with <: n times. From 1 to n with <=: n times. From 0 to n with <=: n+1 times.
- Nested loops (independent): outer count × inner count.
- Nested loops (dependent): sum of inner counts across each outer value. Triangle sums = n(n+1)/2.
- Linear growth (single loop): count doubles when n doubles.
- Quadratic growth (nested loop): count quadruples when n doubles.
Practice Questions
System.out.println(x) execute?for (int x = 5; x <= 15; x++) {
System.out.println(x);
}
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// body
}
}
n = 10, how many times does the marked statement execute?for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
System.out.println("X"); // ← this
}
}
n doubles from 50 to 100, how does the execution count of this loop change?for (int i = 0; i < n; i++) {
System.out.println(i);
}
n doubles from 10 to 20, how does the execution count change for this nested loop?for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(i + j);
}
}
int count = 0;
for (int i = 1; i <= 20; i++) {
if (i % 4 == 0) {
count++; // ← how many times?
}
}
for (int i = 0; i < 100; i++)
for (int i = 0; i < 100; i += 3)
for (int i = 1; i <= 100; i++)
for (int i = 100; i > 0; i--)
System.out.print() execute?for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (i != j) {
System.out.print(i + "" + j);
}
}
}
How many times does the loop body execute?
Mastery: Informal Run-Time Analysis
n = 10, how many times does the inner body execute?for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// body
}
}
n² times, Loop B runs n times. When n=100:i < n to i <= n in a single loop
i++ to i += 2
Get in Touch
Whether you're a student, parent, or teacher — I'd love to hear from you.
Just want free AP CS resources?
Enter your email below and check the subscribe box — no message needed. Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.
Message Sent!
Thanks for reaching out. I'll get back to you within 24 hours.
Prefer email? Reach me directly at [email protected]