Informal Runtime Analysis

Welcome, students! 👋 In this lesson, you will learn how to estimate how long a program takes to run by looking at the number of steps it performs. This is called informal runtime analysis. In AP Computer Science A, you do not need to calculate exact times in seconds or milliseconds. Instead, you learn to compare algorithms by asking: How does the number of operations grow when the input gets bigger?

What you will learn

How to describe the running time of code in a simple way
How to recognize when a loop runs once, many times, or depends on input size
How to compare two algorithms without using a stopwatch ⏱️
How selection and iteration affect the number of operations a program performs
How to connect runtime reasoning to common AP CSA patterns such as $\text{for}$ loops, $\text{while}$ loops, and standard algorithms

Think about a grocery store checkout line. If one cashier checks out one customer at a time, the total time depends on how many customers are waiting. A small line is quick, but a long line takes longer. Informal runtime analysis works the same way: it focuses on how the amount of work changes as input size changes.

What runtime means in AP Computer Science A

In computer science, runtime means how much work a program must do before it finishes. This work is often counted in steps such as comparisons, assignments, and loop repetitions. For AP Computer Science A, the goal is not exact timing on a specific computer. Different computers, programming languages, and compilers can change the actual time. Instead, we analyze the growth of the work.

A useful idea is input size, often written as $n$. If a program processes an array of length $n$, then $n$ is the number of elements in that array. If $n$ increases, we look at whether the number of operations stays about the same, grows slowly, or grows quickly.

For example:

A single print statement usually takes about the same amount of work no matter what $n$ is.
A loop that checks every element in an array usually does more work when $n$ gets larger.
A nested loop can grow much faster than a single loop.

This is why informal runtime analysis is useful. It helps you predict how code behaves on small and large inputs. 📈

Constant time, linear time, and quadratic time

One major job in runtime analysis is describing how work grows.

Constant time

A program or code segment is constant time if it takes about the same amount of work no matter how large the input is. We often describe this as $O(1)$.

Example:

int x = nums[0];

This statement accesses one array element, so the amount of work does not depend on $n$. Even if the array has a million elements, the code still looks at just one position.

Linear time

A program is linear time if the work grows directly with $n$. We often describe this as $O(n)$.

Example:

int sum = 0;
for (int i = 0; i < nums.length; i++) {
    sum += nums[i];
}

This loop examines every element in the array once. If the array has $10$ items, it does about $10$ passes. If it has $100$ items, it does about $100$ passes. That growth is linear.

Quadratic time

A program is quadratic time if the work grows like $n^2$. We often describe this as $O(n^2)$.

Example:

for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < nums.length; j++) {
        System.out.println(nums[i] + nums[j]);
    }
}

Here, for each of the $n$ values of $i$, the inner loop runs $n$ times. That creates about $n \cdot n = n^2$ operations. A quadratic algorithm becomes slow much faster than a linear one as the input grows.

How selection affects runtime

Selection structures, such as $\text{if}$ and $\text{if-else}$, can change the path a program follows. This matters because the runtime may depend on which branch is chosen.

Consider this code:

if (score >= 90) {
    grade = "A";
} else {
    grade = "Not A";
}

The program performs a comparison and then chooses one branch. In informal runtime analysis, a simple $\text{if}$ statement like this is usually treated as constant time, or $O(1)$, because it does not repeat based on $n$.

However, selection can affect how many times a loop runs when used with iteration. For example:

int count = 0;
for (int i = 0; i < nums.length; i++) {
    if (nums[i] > 0) {
        count++;
    }
}

The $\text{if}$ statement is inside the loop. The loop still checks every element, so the overall runtime is linear, $O(n)$. The selection changes what happens inside each pass, but it does not change the fact that the loop runs $n$ times.

This is an important AP CSA idea: a conditional inside a loop does not automatically make the runtime bigger than the loop itself. The loop count matters most.

How iteration affects runtime

Iteration is the heart of runtime analysis. A loop repeats work, and the number of repetitions is the main thing to inspect.

$\text{while}$ loops

A $\text{while}$ loop repeats until a condition becomes false.

Example:

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

This loop runs about $n$ times because $i$ starts at $0$ and increases by $1$ until it reaches $n$. That is linear time, $O(n)$.

A $\text{while}$ loop can be tricky if the update is not obvious. Always ask:

What is the starting value?
How does it change each time?
When does the loop stop?

$\text{for}$ loops

A $\text{for}$ loop is often easier to analyze because the number of repetitions is usually clear.

Example:

for (int k = 1; k <= n; k++) {
    System.out.println(k);
}

This loop runs $n$ times, so it is $O(n)$.

If the loop variable changes by more than $1$, the runtime may still be linear, but the number of iterations must be checked carefully.

Example:

for (int k = 1; k <= n; k = k + 2) {
    System.out.println(k);
}

This loop runs about $n/2$ times. In informal runtime analysis, we still call this $O(n)$ because the number of passes grows proportionally with $n$.

Nested loops and repeated work

Nested loops are a key source of larger runtimes. When one loop is inside another, the total work is often the product of their loop counts.

Example:

for (int row = 0; row < n; row++) {
    for (int col = 0; col < n; col++) {
        System.out.println(row + ", " + col);
    }
}

The outer loop runs $n$ times. For each outer pass, the inner loop also runs $n$ times. So the total number of prints is about $n \cdot n = n^2$. This is why nested loops often lead to quadratic time.

If the inner loop depends on the outer loop, the analysis can be slightly more complex, but AP CSA usually focuses on recognizing the main pattern. For example, if the inner loop runs fewer times each pass, the total may still be close to quadratic or linear depending on the structure.

Standard algorithms and runtime

AP Computer Science A includes standard algorithms such as searching and traversing arrays. Informal runtime analysis helps you understand these algorithms.

Linear search

Linear search checks elements one at a time until it finds the target or reaches the end.

Example:

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

In the worst case, the target is missing or at the last position, so the code checks all $n$ elements. That is $O(n)$.

Finding a maximum

Example:

int max = arr[0];
for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}

The loop scans the array once, so the runtime is $O(n)$.

Binary search

Binary search works on a sorted array and repeatedly cuts the search space in half. This is much faster than linear search for large inputs.

Even though the exact AP CSA level may focus more on recognizing the idea than proving it formally, the key point is that halving the search space makes the growth much slower than linear. That is why binary search is often described as $O(\log n)$.

Informal runtime analysis on the AP exam

On the AP Computer Science A exam, you may be asked to compare two code segments or predict which one is more efficient. To answer well, students, focus on these steps:

Identify how many times each loop repeats.
Look for nested loops, because they often multiply work.
Notice whether a conditional changes the number of loop iterations or only the work inside the loop.
Ignore constant details like one extra assignment or one extra comparison when $n$ grows large.
Use evidence from the code, not guesses.

For example, compare these two methods:

public int methodA(int[] arr) {
    int total = 0;
    for (int i = 0; i < arr.length; i++) {
        total += arr[i];
    }
    return total;
}

public int methodB(int[] arr) {
    int total = 0;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            total += arr[i] + arr[j];
        }
    }
    return total;
}

Method A is $O(n)$. Method B is $O(n^2)$. If the array size grows, Method B will slow down much faster. That is the kind of reasoning the AP exam expects.

Conclusion

Informal runtime analysis helps you understand how code performance changes as input size grows. In AP Computer Science A, the biggest ideas are simple but powerful: constant work stays the same, loops increase work, nested loops multiply work, and selection changes the path but not always the overall growth. By examining $\text{if}$ statements, $\text{while}$ loops, $\text{for}$ loops, and standard algorithms, you can estimate whether code is $O(1)$, $O(n)$, or $O(n^2)$. This skill connects directly to Selection and Iteration because those structures control how many operations a program performs. ✅

Study Notes

Informal runtime analysis estimates how the number of operations grows as input size $n$ increases.
It does not measure exact time in seconds; it compares growth patterns.
Constant time is $O(1)$ and means the work does not depend on $n$.
Linear time is $O(n)$ and means the work grows proportionally with $n$.
Quadratic time is $O(n^2)$ and often comes from nested loops.
A simple $\text{if}$ or $\text{if-else}$ is usually $O(1)$.
A loop that goes through every array element is usually $O(n)$.
Nested loops that each run $n$ times usually give $O(n^2)$.
A conditional inside a loop usually changes the work inside the loop, not the loop count itself.
Linear search and array traversal are typically $O(n)$.
Binary search on a sorted array is much faster for large inputs and is often described as $O(\log n)$.
On AP CSA, explain runtime using evidence from the code, such as loop bounds and nesting.