JAVA / LOOPS AND ARRAYS
Nested loops and their performance cost
Count the work in nested loops as the product of their trip counts, predict how it grows with input size, and cut it by hoisting or removing the inner loop.
What you will learn
- Compute nested loop cost as outer trips x inner trips, never outer plus inner
- Predict growth: 10x the input in an n-squared loop means 100x the inner-body runs
- Hoist loop-invariant calls above the inner loop to divide their count by inner trips
- Recognise hidden nesting when a call like contains() scans the data again
Understanding Nested loops and their performance cost
A nested loop has one body that matters for cost: the innermost one. If the outer header runs n times and the inner header runs m times for each of those, the inner body executes n * m times, so the two levels multiply rather than add. That is why a loop over 1000 items containing a loop over 1000 items is not 2000 steps but 1000000: every outer step pays for a full inner pass. Reading nested loops as a product is the habit that lets you predict cost before you run anything.
Once you see the product, growth follows from it. With both bounds tied to the same n the inner body runs n squared times, so multiplying the input by ten multiplies the work by one hundred, and code that felt instant on 500 rows does about 400 times more work on 10000. Starting the inner loop at i + 1 instead of 0 halves the count to n(n-1)/2, but that is a constant factor and it does not change the shape of the growth. The practical consequence is that quadratic code rarely fails loudly with an exception; it just stops returning.
Because the inner body is the multiplied part, that is also where fixes pay off. Anything in the inner body that does not depend on the inner loop variable can be computed once above the inner loop, which divides its cost by the inner trip count. Watch for nesting with no second for statement in sight: a call to contains, indexOf or a hand-written scan helper hides an inner loop, and building a string with += inside a loop recopies everything written so far on each pass. When the inner work cannot be shrunk, the remaining move is to delete the inner loop by building a lookup once and querying it.
public class NestedLoopCost {
public static void main(String[] args) {
long previous = 0;
for (int n = 10; n <= 10000; n *= 10) {
long steps = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
steps++;
}
}
if (previous == 0) {
System.out.println("n = " + n + " -> inner body ran " + steps + " times");
} else {
System.out.println("n = " + n + " -> inner body ran " + steps
+ " times (" + (steps / previous) + "x the previous row)");
}
previous = steps;
}
}
}Nesting loops multiplies trip counts, so the innermost body is where all the cost lives and where every optimisation has to land.
Worked examples
Hoisting invariant work out of the inner loop
The same result costs 12 calls or 3 calls depending on which loop level the call sits in.
public class Hoisting {
static int upperCalls = 0;
static String upper(String s) {
upperCalls++;
return s.toUpperCase();
}
public static void main(String[] args) {
String[] users = {"ana", "bo", "cy"};
String[] roles = {"read", "write", "admin", "audit"};
int matches = 0;
for (int i = 0; i < users.length; i++) {
for (int j = 0; j < roles.length; j++) {
if (upper(users[i]).startsWith("A")) {
matches++;
}
}
}
System.out.println("call inside inner loop: " + upperCalls + " calls, matches=" + matches);
upperCalls = 0;
matches = 0;
for (int i = 0; i < users.length; i++) {
String u = upper(users[i]);
for (int j = 0; j < roles.length; j++) {
if (u.startsWith("A")) {
matches++;
}
}
}
System.out.println("call hoisted out: " + upperCalls + " calls, matches=" + matches);
}
}Example explained
Line 1upper() bumps a counter, so the printed number is exactly how many times the work was performed.
Line 2In the first pair the call sits inside the j loop, so it runs users.length * roles.length = 12 times although its result depends only on i.
Line 3Assigning it to u above the inner loop drops the count to 3, one per outer pass, and matches stays 4.
Line 4The saving factor is the inner trip count: four roles means one quarter of the calls.
Hidden nesting inside a method call
A single visible for loop still does quadratic work because the helper it calls loops as well.
public class HiddenNesting {
static long comparisons = 0;
static boolean contains(int[] seen, int count, int value) {
for (int i = 0; i < count; i++) {
comparisons++;
if (seen[i] == value) {
return true;
}
}
return false;
}
public static void main(String[] args) {
int[] data = new int[2000];
for (int i = 0; i < data.length; i++) {
data[i] = i;
}
int[] seen = new int[data.length];
int count = 0;
for (int i = 0; i < data.length; i++) {
if (!contains(seen, count, data[i])) {
seen[count] = data[i];
count++;
}
}
System.out.println("distinct=" + count);
System.out.println("comparisons=" + comparisons);
}
}Example explained
Line 1main shows one loop, but contains() walks the filled prefix of seen, so the real structure is two levels deep.
Line 2Every value is distinct, so each call scans all count elements and finds nothing, which is the worst case.
Line 3The total is 0 + 1 + ... + 1999, that is 1999 * 2000 / 2, the 1999000 printed.
Line 4Raising data.length to 4000 would push comparisons to about 8 million, four times as many for twice the input.
Important notes
Nesting is not automatically a bug. With a fixed small bound, such as scanning an 8x8 board, 64 inner steps cost nothing and rewriting it only loses clarity.
Counting inner-body executions predicts growth, not wall-clock time. The JIT can hoist plain arithmetic out of a loop by itself, but it will not hoist a method call whose side effects it cannot rule out, so hoist those yourself.
Common mistakes
Leaving an expensive call such as toUpperCase, parseInt or a regex match in the inner condition, so it runs outer x inner times and the loop is many times slower than the version that computes it once per outer pass.
Building text with result += ... inside a nested loop: each += copies every character produced so far, so copying cost grows with the square of the output length and a small report takes minutes.
Swapping which loop is inner and which is outer to reduce work: 10 x 1000 and 1000 x 10 both run the body 10000 times, so the runtime does not move and the real cost stays hidden.
Try it yourself
Change, predict, then run
Write a nested loop over an array of 6 elements where the inner loop starts at i + 1, count each inner-body run in a long and print it, and confirm you get 15. Then change 6 to 60 and predict the count before you run it.
Open the Java workspaceCheck your understanding
A pair of nested loops, both bounded by n, runs its inner body 10000 times when n = 100. About how many times will the inner body run when n = 400?
- 40000
- 160000
- 1000000
- 10000, because only the outer loop grew
Show answer
The inner body runs n * n times, so multiplying n by 4 multiplies the work by 4 * 4 = 16, giving 160000. Choosing 40000 comes from scaling the previous total by 4, which treats the cost as if only one of the two levels grew.