Big-O is most useful when it helps students predict how code behaves as input gets larger. The goal is not to memorize labels. The goal is to look at a piece of code and ask: what work grows with the input?
Ignore constants, but do not ignore structure
If a loop visits every element once, the runtime is linear. If it visits every pair of elements, the runtime is usually quadratic. If it repeatedly cuts the search space in half, logarithmic behavior may appear.
int count = 0;
for (int i = 0; i < nums.length; i++)
{
for (int j = i + 1; j < nums.length; j++)
{
if (nums[i] == nums[j])
count++;
}
}This code compares many pairs. The exact number is not n squared, but it grows on the order of n squared because the nested loop structure dominates.
Common runtime categories
- O(1): constant work, such as reading one array element.
- O(n): one pass through the data.
- O(n log n): common for efficient comparison sorting.
- O(n^2): nested loops over the same input.
- O(log n): repeated halving, such as binary search.
What students should ask
When analyzing code, identify the input size, count the loops, and ask whether each loop always runs fully or depends on earlier loop variables. That small pause prevents many wrong answers.
Practice idea
Take five methods from old assignments and label the dominant operation. Then rewrite one quadratic method to use a frequency map or sorted data. The improvement becomes much easier to see when students compare both versions.