Counting steps: a first look at efficiency

Written Explanation

What to count

Computers differ in speed, so "it took 3 milliseconds" depends on the machine. A count of steps does not. We pick the operation the algorithm spends its time on, usually the comparison in the innermost loop, and count how often it runs. Other work (increasing i, swapping) is roughly proportional, so it does not change the picture.

The counter is a plain long that every algorithm increments each time it compares. A long is used because counts for large inputs can pass what an int holds comfortably.

static long count;

static int linearSearch(int[] a, int target) {
    for (int i = 0; i < a.length; i++) {
        count++;
        if (a[i] == target) return i;
    }
    return -1;
}

The same count++; goes next to the comparison in the other three methods: before the if that tests a[mid] in binarySearch (inside the loop, counting one per look), and before the if (a[i] > a[i + 1]) of bubble sort, and before the if (a[j] < a[min]) of selection sort. Reset count = 0; before each run.

The experiment

For each size n we use a sorted array {0, 2, 4, ...} and search for the value -1, which is not present and smaller than everything (a missing target forces the search to run to the end). For the sorts we give the reversed array {n, n-1, ..., 1}. These are the demanding inputs.

Real output from running the experiment on JDK 21:

The sorts were not run on a million elements: that would be about 500 billion comparisons, which would take a very long time. That fact is itself the lesson.

The binary column counts the loop iterations when the target is smaller than every element. A missing target that falls elsewhere can take one more look at most, so the true worst case for 1,000 elements is 10; with this input it was 9.

Reading the table: how growth looks

Look at what happens each time n doubles from 10 to 20 to 40.

Linear search: 10, 20, 40. The count doubles each time. Work grows in step with the data. A million elements need a million comparisons.

Binary search: 3, 4, 5. The count goes up by one each time the data doubles. From 1,000 to 1,000,000 (a thousand times more data) it grows only from 9 to 19, which is about 10 more looks. This is the strongest effect in the table.

Bubble and selection sort: 45, 190, 780. Each time n doubles the count multiplies by a little over 4 (190 / 45 is about 4.2, and 780 / 190 is about 4.1). The count is n × (n - 1) / 2, and when n doubles, n × n becomes four times larger, so doubling the data roughly quadruples the work. For 1,000 elements it is already 499,500 comparisons.

Summary in words:

Ranked from slowest-growing to fastest-growing: binary search, linear search, then the two sorts. This ordering is what matters for the data sizes real services meet.

Why not just time it?

Timing is useful (the next lesson does it) but it is noisy: it changes with the machine, other running programs, and how the Java runtime warms up. Counts are exact and repeatable, and they explain the trend. Use counts to understand an algorithm and timings to confirm that your real program behaves as expected.

Be honest about the limits

• We counted one operation. Real cost includes memory access, swaps, and more.
• We tested one kind of input. The comparison count of linear search depends on where the target is, as you saw earlier. Selection sort's count did not change with the input, while bubble sort with an early exit would change.
• Small n can mislead. For n = 10 the difference between 10 and 3 looks small. It becomes decisive only for large data.
• Formal ways of describing growth exist (the topic of BEG-039 in the course plan). Here we only use the words "doubles", "adds one", and "quadruples".