Topic 2.12 Notes – Informal Run-Time Analysis

What Informal Run-Time Analysis Is

When we analyze run time informally, we are counting statement execution counts.

A statement execution count is the number of times a specific line of code runs during program execution.

Example idea:

for (int i = 0; i < arr.length; i++) {
    sum += arr[i];   // How many times does this line run?
}

If arr.length is n, then sum += arr[i]; runs n times.

That’s it. That’s the core skill.

What matters:

• We care about how the count changes as n increases.
• We usually focus on the innermost repeated statement.
• On AP questions, assume worst-case behavior unless told otherwise.
• Constants don’t matter long term:
  • 3n → behaves like n
  • n² + 4n → behaves like n²

The question you should always ask:

How many times does the most repeated line execute?

Recognizing Common Growth Patterns

You don’t need full formal Big-O theory. You need pattern recognition.

Constant Time O(1)

Runs the same number of times no matter how big n gets.

Examples:

• int x = arr[3];
• a = b + c;
• A loop that runs exactly 5 times

If n doubles, the execution count stays the same.

Linear Time O(n)

One loop that depends directly on n.

for (int i = 0; i < arr.length; i++) {
    count++;
}

If the array has n elements, count++ runs n times.

If n doubles → work doubles.

Very common in:

• Searching
• Finding max/min
• Counting or summing

Quadratic Time O(n²)

Nested loops where both depend on n.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        total++;
    }
}

Inner statement runs n × n = n² times.

If n doubles → work becomes 4 times larger.

This shows up in:

• Comparing all pairs
• Duplicate detection (brute force)
• Some sorting algorithms

Visualizing the Difference

Here’s how the growth compares as n increases. The vertical axis shows time and the horizontal axis shows input size.

Common Big-O growth curves

Focus on how the red O(n²) curve rises much faster than the blue O(n) line, and how the green O(1) line stays flat.

Notice how quickly quadratic explodes compared to linear. That’s why recognizing nested loops matters so much.

Counting Executions Step by Step

When analyzing code, move carefully and logically.

Sequential Loops Add

for (int i = 0; i < n; i++) {
    a++;
}

for (int j = 0; j < n; j++) {
    b++;
}

• First loop: n
• Second loop: n
• Total: n + n = 2n → behaves like O(n)

You add sequential sections.

Nested Loops Multiply

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        count++;
    }
}

Outer: n
Inner: n each time

Total: n × n = n²

You multiply nested sections.

Inner Loop Depends on Outer Variable

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        count++;
    }
}

Inner runs:

• n times
• n − 1 times
• n − 2 times
• ...
• 1 time

Total = n(n + 1)/2 → still behaves like n²

Students often think this is “less than n².” It is smaller, but it’s still quadratic growth.

Early Return and Worst Case

for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
        return i;
    }
}

Best case → 1 execution
Worst case → n executions

On most AP questions, you analyze worst case unless they clearly say otherwise.

Common Mistakes That Cost Points

Assuming All Nested Loops Are n²

Check carefully:

• Does the inner loop run n times?
• Or does it run a fixed number like 5?

If inner loop runs 10 times regardless of n:

• n × 10 → still O(n)

Ignoring What’s Inside the Loop

If a loop runs n times but calls something expensive inside it, that matters.

Example idea:

result = result + word;

String concatenation creates a new string each time. As the string grows, each concatenation gets more expensive.

That pattern can lead to quadratic behavior even if there’s only one loop. The AP won’t go deep into advanced libraries, but they absolutely expect you to notice repeated work inside loops.

How This Appears on Tests

You might see:

• “How many times does this statement execute?”
• “What is the run-time complexity?”
• “Which method is more efficient?”

When answering:

1. Identify n.
2. Find the most repeated statement.
3. Decide whether loops add or multiply.
4. Simplify to the dominant growth term.

If you can clearly explain why something runs n times or n² times, you’re thinking exactly the way the exam expects.