Runtime and Big-O for Advanced CS Students

Runtime analysis is not about memorizing labels. It is about identifying which work grows when the input grows. A student who can explain why a method is slow can usually improve it.

Example 1: duplicate detection by pairs

This method checks whether any value appears twice. The structure is the important part: for each index, the inner loop checks later indexes.

public static boolean hasDuplicate(int[] a)
{
    for (int i = 0; i < a.length; i++)
    {
        for (int j = i + 1; j < a.length; j++)
        {
            if (a[i] == a[j])
                return true;
        }
    }
    return false;
}

In the worst case, there is no duplicate, so the method checks all pairs. With 5 items, there are 10 comparisons. With 10 items, there are 45. With 1000 items, there are 499,500. That growth is quadratic, so the method is O(n^2).

Example 2: improving with a set

A set changes the question from "Have I seen this by scanning all earlier values?" to "Have I seen this by lookup?"

public static boolean hasDuplicateFast(int[] a)
{
    HashSet<Integer> seen = new HashSet<>();

    for (int value : a)
    {
        if (seen.contains(value))
            return true;
        seen.add(value);
    }

    return false;
}

For the usual Advanced CS level of reasoning, set lookup is treated as expected constant time. The loop makes one pass, so the expected runtime is O(n). The tradeoff is extra memory for the set.

Hidden costs students miss

Not every single-looking operation is constant. Removing from the front of an ArrayList shifts the remaining elements.

while (list.size() > 0)
{
    list.remove(0);
}

This is not simply O(n). The first removal shifts about n - 1 elements, the next shifts n - 2, and so on. The total is quadratic.

How to analyze code quickly

1. Define n. Is it array length, list size, number of nodes, or number of edges?
2. Find the dominant operation. Comparisons, lookups, shifts, and recursive calls often matter.
3. Check whether loops are independent, nested, or shrinking.
4. Ask whether a library operation hides extra work.

Practice prompt

Compare the runtime of three ways to count how many survey responses use each course label: a nested-loop count, a sorted-list count, and a HashMap<String, Integer> frequency map. Explain both time and memory tradeoffs.