Topic 2.12 — Informal Run-Time Analysis

Goal: describe how an algorithm’s running time grows as input size grows (informally), using ideas like “linear” vs “quadratic,” especially by analyzing loop structures.

The big idea

Run-time analysis isn’t about exact seconds—it’s about growth. As input size (n) gets bigger, how does the number of operations grow?

AP CSA keeps this informal: you mainly compare algorithms by recognizing patterns.

Common growth categories

Pattern	Typical description	What it “feels like”
`O(1)`	constant	doesn’t depend on n
`O(n)`	linear	proportional to n
`O(n^2)`	quadratic	n × n work (often nested loops)

You don’t need advanced proofs—just recognize which category fits.

Constant time: O(1)

A fixed number of operations, regardless of input size.

int x = a + b;
if (x > 10) {
  y++;
}

Linear time: O(n)

One loop that goes through n items once.

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

Quadratic time: O(n²)

A nested loop where each item is paired with many others.

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

Inner body runs about n * n times.

Don’t overthink constants

In informal analysis, you usually ignore constant factors and small additions.

// Still O(n), not “O(2n)”
for (int i = 0; i < n; i++) { ... }
for (int i = 0; i < n; i++) { ... }

How to analyze quickly on AP

Identify how many times the main work repeats.
One loop over n items → likely linear.
Two nested loops over n → likely quadratic.
If bounds aren’t exactly n, still classify by the growth pattern.

Quick self-check

What’s the difference between “exact time” and “growth”?
What kind of loop pattern usually creates O(n²)?
Is two separate loops over n items linear or quadratic?
What does O(1) mean in plain English?
Why do we ignore constants in informal analysis?

← Back to Unit 2 topics