Informal
Run-Time Analysis
Learn to count operations, recognize growth patterns, and classify algorithms using Big-O notation without formal proofs.
AP Computer Science A
What Is Run-Time Analysis?
Run-time analysis answers a fundamental question: how does an algorithm's execution time grow as the input size increases? Instead of measuring wall-clock seconds (which vary by hardware), we count the number of key operations as a function of the input size \( n \).
Why Does Efficiency Matter?
Small Input
When \( n = 10 \), almost every algorithm finishes instantly. Differences are invisible.
Large Input
When \( n = 1{,}000{,}000 \), an \( O(n^2) \) algorithm runs 1 trillion operations while \( O(n \log n) \) runs only ~20 million.
Key Vocabulary
\( n \) : Input Size
The number of elements the algorithm processes (array length, list size, etc.).
Statement Execution Count
How many times a particular line of code runs as a function of \( n \).
Big-O: \( O(\cdot) \)
An upper bound on growth rate. We keep the dominant term and drop constants and lower-order terms.
The Big-O Hierarchy
Core Rule: Drop Constants, Keep Dominant Term
When we write the Big-O for an algorithm, we follow two rules:
1
Drop constant multipliers. If an algorithm runs \( 3n \) operations, we write \( O(n) \), not \( O(3n) \).
2
Keep only the dominant (fastest-growing) term. If it runs \( n^2 + 5n + 100 \) operations, we write \( O(n^2) \) because \( n^2 \) dominates for large \( n \).
Loops Map to Big-O Classes
No loop
Fixed number of statements regardless of \( n \): \( O(1) \)
Single loop
Iterates \( n \) times: \( O(n) \)
Nested loops
Outer runs \( n \) times, inner runs \( n \) times each: \( O(n^2) \)
Halving loop
Loop variable doubles or halves each step: \( O(\log n) \)
Sequential vs. Nested Loops
| Sequential (back-to-back) | Nested (inside each other) | |
|---|---|---|
| Structure | Loop 1 finishes, then Loop 2 starts | Loop 2 runs fully inside each iteration of Loop 1 |
| Operation Count | \( n + n = 2n \) | \( n \times n = n^2 \) |
| Big-O | \( O(n) \) | \( O(n^2) \) |
| Rule | Add the costs | Multiply the costs |
Step-by-Step Analysis
1
Identify the loops. How many loops are there? Are they sequential or nested?
2
Count iterations per loop. Does each loop run \( n \) times? \( n/2 \) times? \( \log n \) times?
3
Combine. Sequential loops: add. Nested loops: multiply.
4
Simplify. Drop constants and lower-order terms to get the Big-O.
Example 1: Single Loop
for (int i = 0; i < n; i++)
{
System.out.println(arr[i]);
}
Example 2: Nested Loops
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
doSomething(i, j);
}
}
Example 3: Halving Loop
int i = n;
while (i > 1)
{
System.out.println(i);
i = i / 2;
}
If \( n = 16 \): the variable \( i \) takes values \( 16, 8, 4, 2 \): that's 4 iterations. Notice that \( \log_2 16 = 4 \).
Example 4: Tricky Nested Loop
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
doWork();
}
}
The inner loop runs \( 0 \) times when \( i=0 \), then \( 1 \), \( 2 \), ... up to \( n-1 \). Total iterations:
Best, Worst, and Average Case
Best Case
The minimum operations for any input of size \( n \). Example: searching a sorted array and finding the target at the first index.
Average Case
The expected operations over all possible inputs of size \( n \). Usually what we care about in practice.
Worst Case
The maximum operations for any input of size \( n \). Big-O typically describes this scenario.
Common Mistakes
✕ Keeping Constants
Writing \( O(3n) \) instead of \( O(n) \). Constants are always dropped in Big-O notation.
✕ Adding Nested Loops
Writing \( O(n + n) \) for nested loops instead of \( O(n \times n) \). Nested means multiply, not add.
✕ Ignoring the Inner Bound
Assuming every inner loop runs exactly \( n \) times. When the inner bound depends on the outer variable (like \( j < i \)), count carefully.
Run-Time Summary
| Code Pattern | Iterations | Big-O |
|---|---|---|
| No loop (fixed statements) | Constant | \( O(1) \) |
| Single loop: 1 to \( n \) | \( n \) | \( O(n) \) |
| Loop halving/doubling | \( \log n \) | \( O(\log n) \) |
| Two sequential loops | \( n + n \) | \( O(n) \) |
| Nested loops (both to \( n \)) | \( n \times n \) | \( O(n^2) \) |
| Loop inside halving loop | \( n \times \log n \) | \( O(n \log n) \) |
Question 1 of 5
for (int i = 0; i < n; i++) { process(arr[i]); } for (int j = 0; j < n; j++) { update(arr[j]); }
▼ Tap to read code
What is the Big-O run time of this code segment?
These are two sequential loops, each running \( n \) times. We add: \( n + n = 2n \). Drop the constant: \( O(n) \).
Question 2 of 5
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { compute(i, j); } }
▼ Tap to read code
What is the Big-O run time of this nested loop?
The outer loop runs \( n \) times. For each outer iteration, the inner loop runs \( n \) times. Nested means multiply: \( n \times n = n^2 \). The answer is \( O(n^2) \).
Question 3 of 5
int x = n; while (x > 1) { x = x / 2; }
▼ Tap to read code
How many times does the while loop execute when \( n = 64 \)?
The variable halves each step: \( 64, 32, 16, 8, 4, 2 \): that is 6 iterations. Since \( \log_2 64 = 6 \), this is an \( O(\log n) \) algorithm.
Question 4 of 5
An algorithm has a statement execution count of \( 5n^2 + 3n + 100 \). What is its Big-O classification?
Drop the constant multiplier (5) and the lower-order terms (\( 3n \) and 100). The dominant term is \( n^2 \), so the answer is \( O(n^2) \).
Question 5 of 5
for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { process(i, j); } }
▼ Tap to read code
What is the Big-O run time of this code segment?
The inner loop runs \( 0, 1, 2, \dots, n-1 \) times. Total: \( \frac{n(n-1)}{2} \). Drop the constant \( \frac{1}{2} \) and the lower-order term: \( O(n^2) \). Even though it's "half" a full grid, it's still quadratic.