Analyzing loops and nested loops

Written Explanation

The procedure

1. Choose the basic operation: the work in the innermost loop, such as one comparison.
2. Count how often it runs as a function of n. For nested loops, multiply the counts; for loops one after the other, add them.
3. Simplify with the two rules from L02 (drop constants, keep the fastest-growing term).

I ran each pattern below with n = 1,000 and counted the basic operation. The counts are real.

Pattern 1: loops one after the other add

for (int i = 0; i < n; i++) steps++;
for (int i = 0; i < n; i++) steps++;

Result: 2,000. That is n + n = 2n, which is O(n). Adding another loop over n makes 3n, still O(n). Do not multiply loops that are not nested.

Pattern 2: nested loops multiply

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        steps++;

Result: 1,000,000, which is n × n, O(n²). If the outer loop runs n times and each time the inner loop runs n times, the body runs n × n times.

What if a quick loop also sits next to the nested pair? Running n steps followed by the nested loops gave 1,001,000, that is n² + n. The n is dropped: O(n²). The nested part dominates.

Pattern 3: the triangular loop

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        steps++;

Result: 499,500. The inner loop runs n - 1 times for the first i, then n - 2, and so on down to 0. The total is n × (n - 1) / 2: for n = 1,000, 1,000 × 999 / 2 = 499,500. This is the same count you met in the bubble sort lesson. It is about half of n × n, but half is a constant, so it is O(n²). A nested loop that "starts later" is not cheaper in Big O.

Pattern 4: the inner loop is a constant

for (int i = 0; i < n; i++)
    for (int j = 0; j < 5; j++)
        steps++;

Result: 5,000, which is 5n, O(n). The inner loop runs a fixed 5 times regardless of n. Nested loops give O(n²) only when both loops grow with n.

Pattern 5: halving and doubling

for (int i = 1; i < n; i *= 2) steps++;

Result: 10. The counter doubles each time: 1, 2, 4, 8, ... , 512, and the loop stops as soon as i reaches n. The number of doublings needed to reach n is about log₂ n, which is 10 for 1,000. Counting down with i /= 2 is the same by symmetry. A loop whose counter is multiplied or divided by a constant is O(log n).

Put that loop inside an n-iteration loop:

for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j *= 2) steps++;

Result: 10,000, which is n × log n, O(n log n). Multiply, as for any nested loop.

Hidden loops

The most expensive mistake is a loop you cannot see. Some library methods contain their own loop:

• list.contains(x) and list.indexOf(x) compare x against elements one by one until a match. For a missing value that is all n elements.
• list.remove(x) has to find x first, and list.remove(index) shifts every later element one place to the left. The ArrayList documentation says get, set, and size run in constant time, add in amortized constant time, and "all of the other operations run in linear time (roughly speaking)". It also says remove(int) shifts the subsequent elements.

A hidden O(n) call inside an O(n) loop gives O(n²), exactly like the nested loops above.

To make this visible I wrote a small class whose equals increments a counter, put 1,000 of them in an ArrayList, and called contains with 1,000 values that are not in the list:

list contains in loop, equals calls: 1000000

That is 1,000 × 1,000. The code has one visible loop and a million comparisons. Putting the same elements in a HashSet and doing the same 1,000 lookups made zero calls to equals in this run, because each lookup went straight to a bucket that did not hold an equal element. The HashSet documentation promises constant-time add, remove, contains, and size, assuming a good hash function; a lookup that finds a bucket with equal-looking entries may still call equals, so this is a trend, not a guarantee of zero.

Two different inputs

If one loop runs over orders (size n) and another over customers (size m), the cost is expressed in both: a nested pair is O(n × m), not O(n²). Do not rename m to n unless the two really are the same size.