PK

PKBytes

Explore tracks
Chapter 4: Complexity, Memory and Performance Analysis
4.03Beginner7 topics16 min7 interactive animations

Loop complexity

Counting loop iterations is the foundation of time analysis. This lesson covers single, nested, non-uniform, halving, dependent, triangular and amortised two-pointer loops, with exact iteration counts you can check in the loop explorer.

Learning goals

  • Count iterations of any loop nest exactly
  • Recognise the n, n², n log n, log n and harmonic patterns
  • Explain why a two-pointer loop is linear

Prerequisites

Common growth functionsSummations and sequences
4.03.1

Single loop

A loop that runs from 0 to n - 1 with a constant step does n iterations, so with constant-time bodies it costs O(n). A step of k gives ⌈n / k⌉ iterations, still linear for fixed k.

Pick the loop shape in the explorer and compare its measured count with the formula.

Java
1for (int i = 0; i < n; i++) work();        // n iterations
2for (int i = 0; i < n; i += 3) work();     // ceil(n / 3) iterations

Counting loop iterations

Interactive · edit the input

Your input

Try

calls per outer step

empty
Setup

Count how many times work() runs for n = 8. Complexity is just this count as a function of n.

Step 1 / 74
Java
1// 0: single loop                      O(n)
2for (int i = 0; i < n; i++) work();
3// 1: nested loops                      O(n^2)
4for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) work();
5// 2: triangular                        O(n^2): n(n-1)/2
6for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) work();
7// 3: halving                           O(log n)
8for (int m = n; m > 1; m /= 2) work();
9// 4: doubling                          O(log n)
10for (int i = 1; i < n; i *= 2) work();
11// 5: linear outer, doubling inner      O(n log n)
12for (int i = 0; i < n; i++) for (int j = 1; j < n; j *= 2) work();
13// 6: two pointers                      O(n) even with a while inside a for
14int j = 0; for (int i = 0; i < n; i++) { while (j < n && cond(i, j)) { work(); j++; } }

Live state

0 work() calls

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 74 steps
StepLineStateWhat happens
1L3n=8Count how many times work() runs for n = 8. Complexity is just this count as a function of n.
2L4i=0Outer i = 0: start the inner loop.
3L4i=0 j=0 work() calls=1(i, j) = (0, 0): n calls for each of the n outer steps.
4L4i=0 j=1 work() calls=2(i, j) = (0, 1): n calls for each of the n outer steps.
5L4i=0 j=2 work() calls=3(i, j) = (0, 2): n calls for each of the n outer steps.
6L4i=0 j=3 work() calls=4(i, j) = (0, 3): n calls for each of the n outer steps.
7L4i=0 j=4 work() calls=5(i, j) = (0, 4): n calls for each of the n outer steps.
8L4i=0 j=5 work() calls=6(i, j) = (0, 5): n calls for each of the n outer steps.
9L4i=0 j=6 work() calls=7(i, j) = (0, 6): n calls for each of the n outer steps.
10L4i=0 j=7 work() calls=8(i, j) = (0, 7): n calls for each of the n outer steps.
11L4i=1Outer i = 1: start the inner loop.
12L4i=1 j=0 work() calls=9(i, j) = (1, 0): n calls for each of the n outer steps.
13L4i=1 j=1 work() calls=10(i, j) = (1, 1): n calls for each of the n outer steps.
14L4i=1 j=2 work() calls=11(i, j) = (1, 2): n calls for each of the n outer steps.
15L4i=1 j=3 work() calls=12(i, j) = (1, 3): n calls for each of the n outer steps.
16L4i=1 j=4 work() calls=13(i, j) = (1, 4): n calls for each of the n outer steps.
17L4i=1 j=5 work() calls=14(i, j) = (1, 5): n calls for each of the n outer steps.
18L4i=1 j=6 work() calls=15(i, j) = (1, 6): n calls for each of the n outer steps.
19L4i=1 j=7 work() calls=16(i, j) = (1, 7): n calls for each of the n outer steps.
20L4i=2Outer i = 2: start the inner loop.
21L4i=2 j=0 work() calls=17(i, j) = (2, 0): n calls for each of the n outer steps.
22L4i=2 j=1 work() calls=18(i, j) = (2, 1): n calls for each of the n outer steps.
23L4i=2 j=2 work() calls=19(i, j) = (2, 2): n calls for each of the n outer steps.
24L4i=2 j=3 work() calls=20(i, j) = (2, 3): n calls for each of the n outer steps.
25L4i=2 j=4 work() calls=21(i, j) = (2, 4): n calls for each of the n outer steps.
26L4i=2 j=5 work() calls=22(i, j) = (2, 5): n calls for each of the n outer steps.
27L4i=2 j=6 work() calls=23(i, j) = (2, 6): n calls for each of the n outer steps.
28L4i=2 j=7 work() calls=24(i, j) = (2, 7): n calls for each of the n outer steps.
29L4i=3Outer i = 3: start the inner loop.
30L4i=3 j=0 work() calls=25(i, j) = (3, 0): n calls for each of the n outer steps.
31L4i=3 j=1 work() calls=26(i, j) = (3, 1): n calls for each of the n outer steps.
32L4i=3 j=2 work() calls=27(i, j) = (3, 2): n calls for each of the n outer steps.
33L4i=3 j=3 work() calls=28(i, j) = (3, 3): n calls for each of the n outer steps.
34L4i=3 j=4 work() calls=29(i, j) = (3, 4): n calls for each of the n outer steps.
35L4i=3 j=5 work() calls=30(i, j) = (3, 5): n calls for each of the n outer steps.
36L4i=3 j=6 work() calls=31(i, j) = (3, 6): n calls for each of the n outer steps.
37L4i=3 j=7 work() calls=32(i, j) = (3, 7): n calls for each of the n outer steps.
38L4i=4Outer i = 4: start the inner loop.
39L4i=4 j=0 work() calls=33(i, j) = (4, 0): n calls for each of the n outer steps.
40L4i=4 j=1 work() calls=34(i, j) = (4, 1): n calls for each of the n outer steps.
41L4i=4 j=2 work() calls=35(i, j) = (4, 2): n calls for each of the n outer steps.
42L4i=4 j=3 work() calls=36(i, j) = (4, 3): n calls for each of the n outer steps.
43L4i=4 j=4 work() calls=37(i, j) = (4, 4): n calls for each of the n outer steps.
44L4i=4 j=5 work() calls=38(i, j) = (4, 5): n calls for each of the n outer steps.
45L4i=4 j=6 work() calls=39(i, j) = (4, 6): n calls for each of the n outer steps.
46L4i=4 j=7 work() calls=40(i, j) = (4, 7): n calls for each of the n outer steps.
47L4i=5Outer i = 5: start the inner loop.
48L4i=5 j=0 work() calls=41(i, j) = (5, 0): n calls for each of the n outer steps.
49L4i=5 j=1 work() calls=42(i, j) = (5, 1): n calls for each of the n outer steps.
50L4i=5 j=2 work() calls=43(i, j) = (5, 2): n calls for each of the n outer steps.
51L4i=5 j=3 work() calls=44(i, j) = (5, 3): n calls for each of the n outer steps.
52L4i=5 j=4 work() calls=45(i, j) = (5, 4): n calls for each of the n outer steps.
53L4i=5 j=5 work() calls=46(i, j) = (5, 5): n calls for each of the n outer steps.
54L4i=5 j=6 work() calls=47(i, j) = (5, 6): n calls for each of the n outer steps.
55L4i=5 j=7 work() calls=48(i, j) = (5, 7): n calls for each of the n outer steps.
56L4i=6Outer i = 6: start the inner loop.
57L4i=6 j=0 work() calls=49(i, j) = (6, 0): n calls for each of the n outer steps.
58L4i=6 j=1 work() calls=50(i, j) = (6, 1): n calls for each of the n outer steps.
59L4i=6 j=2 work() calls=51(i, j) = (6, 2): n calls for each of the n outer steps.
60L4i=6 j=3 work() calls=52(i, j) = (6, 3): n calls for each of the n outer steps.
61L4i=6 j=4 work() calls=53(i, j) = (6, 4): n calls for each of the n outer steps.
62L4i=6 j=5 work() calls=54(i, j) = (6, 5): n calls for each of the n outer steps.
63L4i=6 j=6 work() calls=55(i, j) = (6, 6): n calls for each of the n outer steps.
64L4i=6 j=7 work() calls=56(i, j) = (6, 7): n calls for each of the n outer steps.
65L4i=7Outer i = 7: start the inner loop.
66L4i=7 j=0 work() calls=57(i, j) = (7, 0): n calls for each of the n outer steps.
67L4i=7 j=1 work() calls=58(i, j) = (7, 1): n calls for each of the n outer steps.
68L4i=7 j=2 work() calls=59(i, j) = (7, 2): n calls for each of the n outer steps.
69L4i=7 j=3 work() calls=60(i, j) = (7, 3): n calls for each of the n outer steps.
70L4i=7 j=4 work() calls=61(i, j) = (7, 4): n calls for each of the n outer steps.
71L4i=7 j=5 work() calls=62(i, j) = (7, 5): n calls for each of the n outer steps.
72L4i=7 j=6 work() calls=63(i, j) = (7, 6): n calls for each of the n outer steps.
73L4i=7 j=7 work() calls=64(i, j) = (7, 7): n calls for each of the n outer steps.
74L4n=8 calls=64 return=64work() ran 64 times for n = 8: n². Growth class: O(n²). Change n and watch how the count scales.
4.03.2

Nested loops

When the inner loop's count does not depend on the outer index, multiply: n iterations outside times m inside is n·m, so two loops to n cost n² and three cost n³. Total cost multiplies when loops are nested and adds when they are sequential.

Two loops one after the other, each O(n), still cost O(n).

Java
1for (int i = 0; i < n; i++)
2    for (int j = 0; j < m; j++) work();     // n * m
3for (int i = 0; i < n; i++) work();
4for (int j = 0; j < n; j++) work();         // 2n, still O(n)

Counting loop iterations

Interactive · edit the input

Your input

Try

calls per outer step

empty
Setup

Count how many times work() runs for n = 8. Complexity is just this count as a function of n.

Step 1 / 74
Java
1// 0: single loop                      O(n)
2for (int i = 0; i < n; i++) work();
3// 1: nested loops                      O(n^2)
4for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) work();
5// 2: triangular                        O(n^2): n(n-1)/2
6for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) work();
7// 3: halving                           O(log n)
8for (int m = n; m > 1; m /= 2) work();
9// 4: doubling                          O(log n)
10for (int i = 1; i < n; i *= 2) work();
11// 5: linear outer, doubling inner      O(n log n)
12for (int i = 0; i < n; i++) for (int j = 1; j < n; j *= 2) work();
13// 6: two pointers                      O(n) even with a while inside a for
14int j = 0; for (int i = 0; i < n; i++) { while (j < n && cond(i, j)) { work(); j++; } }

Live state

0 work() calls

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 74 steps
StepLineStateWhat happens
1L3n=8Count how many times work() runs for n = 8. Complexity is just this count as a function of n.
2L4i=0Outer i = 0: start the inner loop.
3L4i=0 j=0 work() calls=1(i, j) = (0, 0): n calls for each of the n outer steps.
4L4i=0 j=1 work() calls=2(i, j) = (0, 1): n calls for each of the n outer steps.
5L4i=0 j=2 work() calls=3(i, j) = (0, 2): n calls for each of the n outer steps.
6L4i=0 j=3 work() calls=4(i, j) = (0, 3): n calls for each of the n outer steps.
7L4i=0 j=4 work() calls=5(i, j) = (0, 4): n calls for each of the n outer steps.
8L4i=0 j=5 work() calls=6(i, j) = (0, 5): n calls for each of the n outer steps.
9L4i=0 j=6 work() calls=7(i, j) = (0, 6): n calls for each of the n outer steps.
10L4i=0 j=7 work() calls=8(i, j) = (0, 7): n calls for each of the n outer steps.
11L4i=1Outer i = 1: start the inner loop.
12L4i=1 j=0 work() calls=9(i, j) = (1, 0): n calls for each of the n outer steps.
13L4i=1 j=1 work() calls=10(i, j) = (1, 1): n calls for each of the n outer steps.
14L4i=1 j=2 work() calls=11(i, j) = (1, 2): n calls for each of the n outer steps.
15L4i=1 j=3 work() calls=12(i, j) = (1, 3): n calls for each of the n outer steps.
16L4i=1 j=4 work() calls=13(i, j) = (1, 4): n calls for each of the n outer steps.
17L4i=1 j=5 work() calls=14(i, j) = (1, 5): n calls for each of the n outer steps.
18L4i=1 j=6 work() calls=15(i, j) = (1, 6): n calls for each of the n outer steps.
19L4i=1 j=7 work() calls=16(i, j) = (1, 7): n calls for each of the n outer steps.
20L4i=2Outer i = 2: start the inner loop.
21L4i=2 j=0 work() calls=17(i, j) = (2, 0): n calls for each of the n outer steps.
22L4i=2 j=1 work() calls=18(i, j) = (2, 1): n calls for each of the n outer steps.
23L4i=2 j=2 work() calls=19(i, j) = (2, 2): n calls for each of the n outer steps.
24L4i=2 j=3 work() calls=20(i, j) = (2, 3): n calls for each of the n outer steps.
25L4i=2 j=4 work() calls=21(i, j) = (2, 4): n calls for each of the n outer steps.
26L4i=2 j=5 work() calls=22(i, j) = (2, 5): n calls for each of the n outer steps.
27L4i=2 j=6 work() calls=23(i, j) = (2, 6): n calls for each of the n outer steps.
28L4i=2 j=7 work() calls=24(i, j) = (2, 7): n calls for each of the n outer steps.
29L4i=3Outer i = 3: start the inner loop.
30L4i=3 j=0 work() calls=25(i, j) = (3, 0): n calls for each of the n outer steps.
31L4i=3 j=1 work() calls=26(i, j) = (3, 1): n calls for each of the n outer steps.
32L4i=3 j=2 work() calls=27(i, j) = (3, 2): n calls for each of the n outer steps.
33L4i=3 j=3 work() calls=28(i, j) = (3, 3): n calls for each of the n outer steps.
34L4i=3 j=4 work() calls=29(i, j) = (3, 4): n calls for each of the n outer steps.
35L4i=3 j=5 work() calls=30(i, j) = (3, 5): n calls for each of the n outer steps.
36L4i=3 j=6 work() calls=31(i, j) = (3, 6): n calls for each of the n outer steps.
37L4i=3 j=7 work() calls=32(i, j) = (3, 7): n calls for each of the n outer steps.
38L4i=4Outer i = 4: start the inner loop.
39L4i=4 j=0 work() calls=33(i, j) = (4, 0): n calls for each of the n outer steps.
40L4i=4 j=1 work() calls=34(i, j) = (4, 1): n calls for each of the n outer steps.
41L4i=4 j=2 work() calls=35(i, j) = (4, 2): n calls for each of the n outer steps.
42L4i=4 j=3 work() calls=36(i, j) = (4, 3): n calls for each of the n outer steps.
43L4i=4 j=4 work() calls=37(i, j) = (4, 4): n calls for each of the n outer steps.
44L4i=4 j=5 work() calls=38(i, j) = (4, 5): n calls for each of the n outer steps.
45L4i=4 j=6 work() calls=39(i, j) = (4, 6): n calls for each of the n outer steps.
46L4i=4 j=7 work() calls=40(i, j) = (4, 7): n calls for each of the n outer steps.
47L4i=5Outer i = 5: start the inner loop.
48L4i=5 j=0 work() calls=41(i, j) = (5, 0): n calls for each of the n outer steps.
49L4i=5 j=1 work() calls=42(i, j) = (5, 1): n calls for each of the n outer steps.
50L4i=5 j=2 work() calls=43(i, j) = (5, 2): n calls for each of the n outer steps.
51L4i=5 j=3 work() calls=44(i, j) = (5, 3): n calls for each of the n outer steps.
52L4i=5 j=4 work() calls=45(i, j) = (5, 4): n calls for each of the n outer steps.
53L4i=5 j=5 work() calls=46(i, j) = (5, 5): n calls for each of the n outer steps.
54L4i=5 j=6 work() calls=47(i, j) = (5, 6): n calls for each of the n outer steps.
55L4i=5 j=7 work() calls=48(i, j) = (5, 7): n calls for each of the n outer steps.
56L4i=6Outer i = 6: start the inner loop.
57L4i=6 j=0 work() calls=49(i, j) = (6, 0): n calls for each of the n outer steps.
58L4i=6 j=1 work() calls=50(i, j) = (6, 1): n calls for each of the n outer steps.
59L4i=6 j=2 work() calls=51(i, j) = (6, 2): n calls for each of the n outer steps.
60L4i=6 j=3 work() calls=52(i, j) = (6, 3): n calls for each of the n outer steps.
61L4i=6 j=4 work() calls=53(i, j) = (6, 4): n calls for each of the n outer steps.
62L4i=6 j=5 work() calls=54(i, j) = (6, 5): n calls for each of the n outer steps.
63L4i=6 j=6 work() calls=55(i, j) = (6, 6): n calls for each of the n outer steps.
64L4i=6 j=7 work() calls=56(i, j) = (6, 7): n calls for each of the n outer steps.
65L4i=7Outer i = 7: start the inner loop.
66L4i=7 j=0 work() calls=57(i, j) = (7, 0): n calls for each of the n outer steps.
67L4i=7 j=1 work() calls=58(i, j) = (7, 1): n calls for each of the n outer steps.
68L4i=7 j=2 work() calls=59(i, j) = (7, 2): n calls for each of the n outer steps.
69L4i=7 j=3 work() calls=60(i, j) = (7, 3): n calls for each of the n outer steps.
70L4i=7 j=4 work() calls=61(i, j) = (7, 4): n calls for each of the n outer steps.
71L4i=7 j=5 work() calls=62(i, j) = (7, 5): n calls for each of the n outer steps.
72L4i=7 j=6 work() calls=63(i, j) = (7, 6): n calls for each of the n outer steps.
73L4i=7 j=7 work() calls=64(i, j) = (7, 7): n calls for each of the n outer steps.
74L4n=8 calls=64 return=64work() ran 64 times for n = 8: n². Growth class: O(n²). Change n and watch how the count scales.
4.03.3

Non-uniform loops

Sometimes the inner loop runs only for some outer iterations, or its cost changes with a condition. Count how often the inner loop is entered times its cost. If it runs for every second value of i, the total is (n/2) · n = n²/2, still Θ(n²).

Constant fractions do not change the class; a fraction that shrinks with n does.

Java
1for (int i = 0; i < n; i++)
2    if (i % 2 == 0)
3        for (int j = 0; j < n; j++) work();   // n/2 * n = n^2 / 2

Counting loop iterations

Interactive · edit the input

Your input

Try

calls per outer step

empty
Setup

Count how many times work() runs for n = 8. Complexity is just this count as a function of n.

Step 1 / 74
Java
1// 0: single loop                      O(n)
2for (int i = 0; i < n; i++) work();
3// 1: nested loops                      O(n^2)
4for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) work();
5// 2: triangular                        O(n^2): n(n-1)/2
6for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) work();
7// 3: halving                           O(log n)
8for (int m = n; m > 1; m /= 2) work();
9// 4: doubling                          O(log n)
10for (int i = 1; i < n; i *= 2) work();
11// 5: linear outer, doubling inner      O(n log n)
12for (int i = 0; i < n; i++) for (int j = 1; j < n; j *= 2) work();
13// 6: two pointers                      O(n) even with a while inside a for
14int j = 0; for (int i = 0; i < n; i++) { while (j < n && cond(i, j)) { work(); j++; } }

Live state

0 work() calls

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 74 steps
StepLineStateWhat happens
1L3n=8Count how many times work() runs for n = 8. Complexity is just this count as a function of n.
2L4i=0Outer i = 0: start the inner loop.
3L4i=0 j=0 work() calls=1(i, j) = (0, 0): n calls for each of the n outer steps.
4L4i=0 j=1 work() calls=2(i, j) = (0, 1): n calls for each of the n outer steps.
5L4i=0 j=2 work() calls=3(i, j) = (0, 2): n calls for each of the n outer steps.
6L4i=0 j=3 work() calls=4(i, j) = (0, 3): n calls for each of the n outer steps.
7L4i=0 j=4 work() calls=5(i, j) = (0, 4): n calls for each of the n outer steps.
8L4i=0 j=5 work() calls=6(i, j) = (0, 5): n calls for each of the n outer steps.
9L4i=0 j=6 work() calls=7(i, j) = (0, 6): n calls for each of the n outer steps.
10L4i=0 j=7 work() calls=8(i, j) = (0, 7): n calls for each of the n outer steps.
11L4i=1Outer i = 1: start the inner loop.
12L4i=1 j=0 work() calls=9(i, j) = (1, 0): n calls for each of the n outer steps.
13L4i=1 j=1 work() calls=10(i, j) = (1, 1): n calls for each of the n outer steps.
14L4i=1 j=2 work() calls=11(i, j) = (1, 2): n calls for each of the n outer steps.
15L4i=1 j=3 work() calls=12(i, j) = (1, 3): n calls for each of the n outer steps.
16L4i=1 j=4 work() calls=13(i, j) = (1, 4): n calls for each of the n outer steps.
17L4i=1 j=5 work() calls=14(i, j) = (1, 5): n calls for each of the n outer steps.
18L4i=1 j=6 work() calls=15(i, j) = (1, 6): n calls for each of the n outer steps.
19L4i=1 j=7 work() calls=16(i, j) = (1, 7): n calls for each of the n outer steps.
20L4i=2Outer i = 2: start the inner loop.
21L4i=2 j=0 work() calls=17(i, j) = (2, 0): n calls for each of the n outer steps.
22L4i=2 j=1 work() calls=18(i, j) = (2, 1): n calls for each of the n outer steps.
23L4i=2 j=2 work() calls=19(i, j) = (2, 2): n calls for each of the n outer steps.
24L4i=2 j=3 work() calls=20(i, j) = (2, 3): n calls for each of the n outer steps.
25L4i=2 j=4 work() calls=21(i, j) = (2, 4): n calls for each of the n outer steps.
26L4i=2 j=5 work() calls=22(i, j) = (2, 5): n calls for each of the n outer steps.
27L4i=2 j=6 work() calls=23(i, j) = (2, 6): n calls for each of the n outer steps.
28L4i=2 j=7 work() calls=24(i, j) = (2, 7): n calls for each of the n outer steps.
29L4i=3Outer i = 3: start the inner loop.
30L4i=3 j=0 work() calls=25(i, j) = (3, 0): n calls for each of the n outer steps.
31L4i=3 j=1 work() calls=26(i, j) = (3, 1): n calls for each of the n outer steps.
32L4i=3 j=2 work() calls=27(i, j) = (3, 2): n calls for each of the n outer steps.
33L4i=3 j=3 work() calls=28(i, j) = (3, 3): n calls for each of the n outer steps.
34L4i=3 j=4 work() calls=29(i, j) = (3, 4): n calls for each of the n outer steps.
35L4i=3 j=5 work() calls=30(i, j) = (3, 5): n calls for each of the n outer steps.
36L4i=3 j=6 work() calls=31(i, j) = (3, 6): n calls for each of the n outer steps.
37L4i=3 j=7 work() calls=32(i, j) = (3, 7): n calls for each of the n outer steps.
38L4i=4Outer i = 4: start the inner loop.
39L4i=4 j=0 work() calls=33(i, j) = (4, 0): n calls for each of the n outer steps.
40L4i=4 j=1 work() calls=34(i, j) = (4, 1): n calls for each of the n outer steps.
41L4i=4 j=2 work() calls=35(i, j) = (4, 2): n calls for each of the n outer steps.
42L4i=4 j=3 work() calls=36(i, j) = (4, 3): n calls for each of the n outer steps.
43L4i=4 j=4 work() calls=37(i, j) = (4, 4): n calls for each of the n outer steps.
44L4i=4 j=5 work() calls=38(i, j) = (4, 5): n calls for each of the n outer steps.
45L4i=4 j=6 work() calls=39(i, j) = (4, 6): n calls for each of the n outer steps.
46L4i=4 j=7 work() calls=40(i, j) = (4, 7): n calls for each of the n outer steps.
47L4i=5Outer i = 5: start the inner loop.
48L4i=5 j=0 work() calls=41(i, j) = (5, 0): n calls for each of the n outer steps.
49L4i=5 j=1 work() calls=42(i, j) = (5, 1): n calls for each of the n outer steps.
50L4i=5 j=2 work() calls=43(i, j) = (5, 2): n calls for each of the n outer steps.
51L4i=5 j=3 work() calls=44(i, j) = (5, 3): n calls for each of the n outer steps.
52L4i=5 j=4 work() calls=45(i, j) = (5, 4): n calls for each of the n outer steps.
53L4i=5 j=5 work() calls=46(i, j) = (5, 5): n calls for each of the n outer steps.
54L4i=5 j=6 work() calls=47(i, j) = (5, 6): n calls for each of the n outer steps.
55L4i=5 j=7 work() calls=48(i, j) = (5, 7): n calls for each of the n outer steps.
56L4i=6Outer i = 6: start the inner loop.
57L4i=6 j=0 work() calls=49(i, j) = (6, 0): n calls for each of the n outer steps.
58L4i=6 j=1 work() calls=50(i, j) = (6, 1): n calls for each of the n outer steps.
59L4i=6 j=2 work() calls=51(i, j) = (6, 2): n calls for each of the n outer steps.
60L4i=6 j=3 work() calls=52(i, j) = (6, 3): n calls for each of the n outer steps.
61L4i=6 j=4 work() calls=53(i, j) = (6, 4): n calls for each of the n outer steps.
62L4i=6 j=5 work() calls=54(i, j) = (6, 5): n calls for each of the n outer steps.
63L4i=6 j=6 work() calls=55(i, j) = (6, 6): n calls for each of the n outer steps.
64L4i=6 j=7 work() calls=56(i, j) = (6, 7): n calls for each of the n outer steps.
65L4i=7Outer i = 7: start the inner loop.
66L4i=7 j=0 work() calls=57(i, j) = (7, 0): n calls for each of the n outer steps.
67L4i=7 j=1 work() calls=58(i, j) = (7, 1): n calls for each of the n outer steps.
68L4i=7 j=2 work() calls=59(i, j) = (7, 2): n calls for each of the n outer steps.
69L4i=7 j=3 work() calls=60(i, j) = (7, 3): n calls for each of the n outer steps.
70L4i=7 j=4 work() calls=61(i, j) = (7, 4): n calls for each of the n outer steps.
71L4i=7 j=5 work() calls=62(i, j) = (7, 5): n calls for each of the n outer steps.
72L4i=7 j=6 work() calls=63(i, j) = (7, 6): n calls for each of the n outer steps.
73L4i=7 j=7 work() calls=64(i, j) = (7, 7): n calls for each of the n outer steps.
74L4n=8 calls=64 return=64work() ran 64 times for n = 8: n². Growth class: O(n²). Change n and watch how the count scales.
4.03.4

Halving and doubling

A loop that multiplies or divides its counter by a constant each time runs a logarithmic number of times. for (i = 1; i < n; i *= 2) executes ⌈log₂ n⌉ times (n = 16 gives 4, n = 17 gives 5). Nested inside a linear loop it gives n log n.

Observe the exact counts for both directions in the explorer.

Java
1for (int i = 1; i < n; i *= 2) work();          // ceil(log2 n)
2for (int i = n; i > 0; i /= 2) work();          // floor(log2 n) + 1
3for (int i = 0; i < n; i++)
4    for (int j = 1; j < n; j *= 2) work();       // n * ceil(log2 n)

Counting loop iterations

Interactive · edit the input

Your input

Try

calls per outer step

empty
Setup

Count how many times work() runs for n = 8. Complexity is just this count as a function of n.

Step 1 / 74
Java
1// 0: single loop                      O(n)
2for (int i = 0; i < n; i++) work();
3// 1: nested loops                      O(n^2)
4for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) work();
5// 2: triangular                        O(n^2): n(n-1)/2
6for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) work();
7// 3: halving                           O(log n)
8for (int m = n; m > 1; m /= 2) work();
9// 4: doubling                          O(log n)
10for (int i = 1; i < n; i *= 2) work();
11// 5: linear outer, doubling inner      O(n log n)
12for (int i = 0; i < n; i++) for (int j = 1; j < n; j *= 2) work();
13// 6: two pointers                      O(n) even with a while inside a for
14int j = 0; for (int i = 0; i < n; i++) { while (j < n && cond(i, j)) { work(); j++; } }

Live state

0 work() calls

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 74 steps
StepLineStateWhat happens
1L3n=8Count how many times work() runs for n = 8. Complexity is just this count as a function of n.
2L4i=0Outer i = 0: start the inner loop.
3L4i=0 j=0 work() calls=1(i, j) = (0, 0): n calls for each of the n outer steps.
4L4i=0 j=1 work() calls=2(i, j) = (0, 1): n calls for each of the n outer steps.
5L4i=0 j=2 work() calls=3(i, j) = (0, 2): n calls for each of the n outer steps.
6L4i=0 j=3 work() calls=4(i, j) = (0, 3): n calls for each of the n outer steps.
7L4i=0 j=4 work() calls=5(i, j) = (0, 4): n calls for each of the n outer steps.
8L4i=0 j=5 work() calls=6(i, j) = (0, 5): n calls for each of the n outer steps.
9L4i=0 j=6 work() calls=7(i, j) = (0, 6): n calls for each of the n outer steps.
10L4i=0 j=7 work() calls=8(i, j) = (0, 7): n calls for each of the n outer steps.
11L4i=1Outer i = 1: start the inner loop.
12L4i=1 j=0 work() calls=9(i, j) = (1, 0): n calls for each of the n outer steps.
13L4i=1 j=1 work() calls=10(i, j) = (1, 1): n calls for each of the n outer steps.
14L4i=1 j=2 work() calls=11(i, j) = (1, 2): n calls for each of the n outer steps.
15L4i=1 j=3 work() calls=12(i, j) = (1, 3): n calls for each of the n outer steps.
16L4i=1 j=4 work() calls=13(i, j) = (1, 4): n calls for each of the n outer steps.
17L4i=1 j=5 work() calls=14(i, j) = (1, 5): n calls for each of the n outer steps.
18L4i=1 j=6 work() calls=15(i, j) = (1, 6): n calls for each of the n outer steps.
19L4i=1 j=7 work() calls=16(i, j) = (1, 7): n calls for each of the n outer steps.
20L4i=2Outer i = 2: start the inner loop.
21L4i=2 j=0 work() calls=17(i, j) = (2, 0): n calls for each of the n outer steps.
22L4i=2 j=1 work() calls=18(i, j) = (2, 1): n calls for each of the n outer steps.
23L4i=2 j=2 work() calls=19(i, j) = (2, 2): n calls for each of the n outer steps.
24L4i=2 j=3 work() calls=20(i, j) = (2, 3): n calls for each of the n outer steps.
25L4i=2 j=4 work() calls=21(i, j) = (2, 4): n calls for each of the n outer steps.
26L4i=2 j=5 work() calls=22(i, j) = (2, 5): n calls for each of the n outer steps.
27L4i=2 j=6 work() calls=23(i, j) = (2, 6): n calls for each of the n outer steps.
28L4i=2 j=7 work() calls=24(i, j) = (2, 7): n calls for each of the n outer steps.
29L4i=3Outer i = 3: start the inner loop.
30L4i=3 j=0 work() calls=25(i, j) = (3, 0): n calls for each of the n outer steps.
31L4i=3 j=1 work() calls=26(i, j) = (3, 1): n calls for each of the n outer steps.
32L4i=3 j=2 work() calls=27(i, j) = (3, 2): n calls for each of the n outer steps.
33L4i=3 j=3 work() calls=28(i, j) = (3, 3): n calls for each of the n outer steps.
34L4i=3 j=4 work() calls=29(i, j) = (3, 4): n calls for each of the n outer steps.
35L4i=3 j=5 work() calls=30(i, j) = (3, 5): n calls for each of the n outer steps.
36L4i=3 j=6 work() calls=31(i, j) = (3, 6): n calls for each of the n outer steps.
37L4i=3 j=7 work() calls=32(i, j) = (3, 7): n calls for each of the n outer steps.
38L4i=4Outer i = 4: start the inner loop.
39L4i=4 j=0 work() calls=33(i, j) = (4, 0): n calls for each of the n outer steps.
40L4i=4 j=1 work() calls=34(i, j) = (4, 1): n calls for each of the n outer steps.
41L4i=4 j=2 work() calls=35(i, j) = (4, 2): n calls for each of the n outer steps.
42L4i=4 j=3 work() calls=36(i, j) = (4, 3): n calls for each of the n outer steps.
43L4i=4 j=4 work() calls=37(i, j) = (4, 4): n calls for each of the n outer steps.
44L4i=4 j=5 work() calls=38(i, j) = (4, 5): n calls for each of the n outer steps.
45L4i=4 j=6 work() calls=39(i, j) = (4, 6): n calls for each of the n outer steps.
46L4i=4 j=7 work() calls=40(i, j) = (4, 7): n calls for each of the n outer steps.
47L4i=5Outer i = 5: start the inner loop.
48L4i=5 j=0 work() calls=41(i, j) = (5, 0): n calls for each of the n outer steps.
49L4i=5 j=1 work() calls=42(i, j) = (5, 1): n calls for each of the n outer steps.
50L4i=5 j=2 work() calls=43(i, j) = (5, 2): n calls for each of the n outer steps.
51L4i=5 j=3 work() calls=44(i, j) = (5, 3): n calls for each of the n outer steps.
52L4i=5 j=4 work() calls=45(i, j) = (5, 4): n calls for each of the n outer steps.
53L4i=5 j=5 work() calls=46(i, j) = (5, 5): n calls for each of the n outer steps.
54L4i=5 j=6 work() calls=47(i, j) = (5, 6): n calls for each of the n outer steps.
55L4i=5 j=7 work() calls=48(i, j) = (5, 7): n calls for each of the n outer steps.
56L4i=6Outer i = 6: start the inner loop.
57L4i=6 j=0 work() calls=49(i, j) = (6, 0): n calls for each of the n outer steps.
58L4i=6 j=1 work() calls=50(i, j) = (6, 1): n calls for each of the n outer steps.
59L4i=6 j=2 work() calls=51(i, j) = (6, 2): n calls for each of the n outer steps.
60L4i=6 j=3 work() calls=52(i, j) = (6, 3): n calls for each of the n outer steps.
61L4i=6 j=4 work() calls=53(i, j) = (6, 4): n calls for each of the n outer steps.
62L4i=6 j=5 work() calls=54(i, j) = (6, 5): n calls for each of the n outer steps.
63L4i=6 j=6 work() calls=55(i, j) = (6, 6): n calls for each of the n outer steps.
64L4i=6 j=7 work() calls=56(i, j) = (6, 7): n calls for each of the n outer steps.
65L4i=7Outer i = 7: start the inner loop.
66L4i=7 j=0 work() calls=57(i, j) = (7, 0): n calls for each of the n outer steps.
67L4i=7 j=1 work() calls=58(i, j) = (7, 1): n calls for each of the n outer steps.
68L4i=7 j=2 work() calls=59(i, j) = (7, 2): n calls for each of the n outer steps.
69L4i=7 j=3 work() calls=60(i, j) = (7, 3): n calls for each of the n outer steps.
70L4i=7 j=4 work() calls=61(i, j) = (7, 4): n calls for each of the n outer steps.
71L4i=7 j=5 work() calls=62(i, j) = (7, 5): n calls for each of the n outer steps.
72L4i=7 j=6 work() calls=63(i, j) = (7, 6): n calls for each of the n outer steps.
73L4i=7 j=7 work() calls=64(i, j) = (7, 7): n calls for each of the n outer steps.
74L4n=8 calls=64 return=64work() ran 64 times for n = 8: n². Growth class: O(n²). Change n and watch how the count scales.
4.03.5

Dependent loop bounds

When the inner bound depends on the outer variable, sum the inner counts. For for i in 0..n-1: for j in 0..i-1 the inner loop runs 0 + 1 + … + (n - 1) = n(n - 1)/2 times. For for i: for (j = i; j < n; j += i) the counts sum to about n · Hₙ = O(n log n).

Write the sum, then use a formula from Summations and sequences.

Java
1int count = 0;
2for (int i = 1; i <= n; i++)
3    for (int j = i; j <= n; j += i) count++;    // about n * ln(n) iterations

Counting loop iterations

Interactive · edit the input

Your input

Try

calls per outer step

empty
Setup

Count how many times work() runs for n = 8. Complexity is just this count as a function of n.

Step 1 / 74
Java
1// 0: single loop                      O(n)
2for (int i = 0; i < n; i++) work();
3// 1: nested loops                      O(n^2)
4for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) work();
5// 2: triangular                        O(n^2): n(n-1)/2
6for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) work();
7// 3: halving                           O(log n)
8for (int m = n; m > 1; m /= 2) work();
9// 4: doubling                          O(log n)
10for (int i = 1; i < n; i *= 2) work();
11// 5: linear outer, doubling inner      O(n log n)
12for (int i = 0; i < n; i++) for (int j = 1; j < n; j *= 2) work();
13// 6: two pointers                      O(n) even with a while inside a for
14int j = 0; for (int i = 0; i < n; i++) { while (j < n && cond(i, j)) { work(); j++; } }

Live state

0 work() calls

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 74 steps
StepLineStateWhat happens
1L3n=8Count how many times work() runs for n = 8. Complexity is just this count as a function of n.
2L4i=0Outer i = 0: start the inner loop.
3L4i=0 j=0 work() calls=1(i, j) = (0, 0): n calls for each of the n outer steps.
4L4i=0 j=1 work() calls=2(i, j) = (0, 1): n calls for each of the n outer steps.
5L4i=0 j=2 work() calls=3(i, j) = (0, 2): n calls for each of the n outer steps.
6L4i=0 j=3 work() calls=4(i, j) = (0, 3): n calls for each of the n outer steps.
7L4i=0 j=4 work() calls=5(i, j) = (0, 4): n calls for each of the n outer steps.
8L4i=0 j=5 work() calls=6(i, j) = (0, 5): n calls for each of the n outer steps.
9L4i=0 j=6 work() calls=7(i, j) = (0, 6): n calls for each of the n outer steps.
10L4i=0 j=7 work() calls=8(i, j) = (0, 7): n calls for each of the n outer steps.
11L4i=1Outer i = 1: start the inner loop.
12L4i=1 j=0 work() calls=9(i, j) = (1, 0): n calls for each of the n outer steps.
13L4i=1 j=1 work() calls=10(i, j) = (1, 1): n calls for each of the n outer steps.
14L4i=1 j=2 work() calls=11(i, j) = (1, 2): n calls for each of the n outer steps.
15L4i=1 j=3 work() calls=12(i, j) = (1, 3): n calls for each of the n outer steps.
16L4i=1 j=4 work() calls=13(i, j) = (1, 4): n calls for each of the n outer steps.
17L4i=1 j=5 work() calls=14(i, j) = (1, 5): n calls for each of the n outer steps.
18L4i=1 j=6 work() calls=15(i, j) = (1, 6): n calls for each of the n outer steps.
19L4i=1 j=7 work() calls=16(i, j) = (1, 7): n calls for each of the n outer steps.
20L4i=2Outer i = 2: start the inner loop.
21L4i=2 j=0 work() calls=17(i, j) = (2, 0): n calls for each of the n outer steps.
22L4i=2 j=1 work() calls=18(i, j) = (2, 1): n calls for each of the n outer steps.
23L4i=2 j=2 work() calls=19(i, j) = (2, 2): n calls for each of the n outer steps.
24L4i=2 j=3 work() calls=20(i, j) = (2, 3): n calls for each of the n outer steps.
25L4i=2 j=4 work() calls=21(i, j) = (2, 4): n calls for each of the n outer steps.
26L4i=2 j=5 work() calls=22(i, j) = (2, 5): n calls for each of the n outer steps.
27L4i=2 j=6 work() calls=23(i, j) = (2, 6): n calls for each of the n outer steps.
28L4i=2 j=7 work() calls=24(i, j) = (2, 7): n calls for each of the n outer steps.
29L4i=3Outer i = 3: start the inner loop.
30L4i=3 j=0 work() calls=25(i, j) = (3, 0): n calls for each of the n outer steps.
31L4i=3 j=1 work() calls=26(i, j) = (3, 1): n calls for each of the n outer steps.
32L4i=3 j=2 work() calls=27(i, j) = (3, 2): n calls for each of the n outer steps.
33L4i=3 j=3 work() calls=28(i, j) = (3, 3): n calls for each of the n outer steps.
34L4i=3 j=4 work() calls=29(i, j) = (3, 4): n calls for each of the n outer steps.
35L4i=3 j=5 work() calls=30(i, j) = (3, 5): n calls for each of the n outer steps.
36L4i=3 j=6 work() calls=31(i, j) = (3, 6): n calls for each of the n outer steps.
37L4i=3 j=7 work() calls=32(i, j) = (3, 7): n calls for each of the n outer steps.
38L4i=4Outer i = 4: start the inner loop.
39L4i=4 j=0 work() calls=33(i, j) = (4, 0): n calls for each of the n outer steps.
40L4i=4 j=1 work() calls=34(i, j) = (4, 1): n calls for each of the n outer steps.
41L4i=4 j=2 work() calls=35(i, j) = (4, 2): n calls for each of the n outer steps.
42L4i=4 j=3 work() calls=36(i, j) = (4, 3): n calls for each of the n outer steps.
43L4i=4 j=4 work() calls=37(i, j) = (4, 4): n calls for each of the n outer steps.
44L4i=4 j=5 work() calls=38(i, j) = (4, 5): n calls for each of the n outer steps.
45L4i=4 j=6 work() calls=39(i, j) = (4, 6): n calls for each of the n outer steps.
46L4i=4 j=7 work() calls=40(i, j) = (4, 7): n calls for each of the n outer steps.
47L4i=5Outer i = 5: start the inner loop.
48L4i=5 j=0 work() calls=41(i, j) = (5, 0): n calls for each of the n outer steps.
49L4i=5 j=1 work() calls=42(i, j) = (5, 1): n calls for each of the n outer steps.
50L4i=5 j=2 work() calls=43(i, j) = (5, 2): n calls for each of the n outer steps.
51L4i=5 j=3 work() calls=44(i, j) = (5, 3): n calls for each of the n outer steps.
52L4i=5 j=4 work() calls=45(i, j) = (5, 4): n calls for each of the n outer steps.
53L4i=5 j=5 work() calls=46(i, j) = (5, 5): n calls for each of the n outer steps.
54L4i=5 j=6 work() calls=47(i, j) = (5, 6): n calls for each of the n outer steps.
55L4i=5 j=7 work() calls=48(i, j) = (5, 7): n calls for each of the n outer steps.
56L4i=6Outer i = 6: start the inner loop.
57L4i=6 j=0 work() calls=49(i, j) = (6, 0): n calls for each of the n outer steps.
58L4i=6 j=1 work() calls=50(i, j) = (6, 1): n calls for each of the n outer steps.
59L4i=6 j=2 work() calls=51(i, j) = (6, 2): n calls for each of the n outer steps.
60L4i=6 j=3 work() calls=52(i, j) = (6, 3): n calls for each of the n outer steps.
61L4i=6 j=4 work() calls=53(i, j) = (6, 4): n calls for each of the n outer steps.
62L4i=6 j=5 work() calls=54(i, j) = (6, 5): n calls for each of the n outer steps.
63L4i=6 j=6 work() calls=55(i, j) = (6, 6): n calls for each of the n outer steps.
64L4i=6 j=7 work() calls=56(i, j) = (6, 7): n calls for each of the n outer steps.
65L4i=7Outer i = 7: start the inner loop.
66L4i=7 j=0 work() calls=57(i, j) = (7, 0): n calls for each of the n outer steps.
67L4i=7 j=1 work() calls=58(i, j) = (7, 1): n calls for each of the n outer steps.
68L4i=7 j=2 work() calls=59(i, j) = (7, 2): n calls for each of the n outer steps.
69L4i=7 j=3 work() calls=60(i, j) = (7, 3): n calls for each of the n outer steps.
70L4i=7 j=4 work() calls=61(i, j) = (7, 4): n calls for each of the n outer steps.
71L4i=7 j=5 work() calls=62(i, j) = (7, 5): n calls for each of the n outer steps.
72L4i=7 j=6 work() calls=63(i, j) = (7, 6): n calls for each of the n outer steps.
73L4i=7 j=7 work() calls=64(i, j) = (7, 7): n calls for each of the n outer steps.
74L4n=8 calls=64 return=64work() ran 64 times for n = 8: n². Growth class: O(n²). Change n and watch how the count scales.
4.03.6

Triangular loops

A triangular loop nest has n(n ± 1)/2 iterations: half of a square. It is Θ(n²) with a constant of ½. Examples: comparing every pair once, insertion sort's worst case, and building a Pascal triangle.

Check n = 5: the pattern j < i gives 0 + 1 + 2 + 3 + 4 = 10 = 5·4/2.

Java
1int steps = 0;
2for (int i = 0; i < n; i++)
3    for (int j = 0; j < i; j++) steps++;     // n(n-1)/2

Counting loop iterations

Interactive · edit the input

Your input

Try

calls per outer step

empty
Setup

Count how many times work() runs for n = 8. Complexity is just this count as a function of n.

Step 1 / 74
Java
1// 0: single loop                      O(n)
2for (int i = 0; i < n; i++) work();
3// 1: nested loops                      O(n^2)
4for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) work();
5// 2: triangular                        O(n^2): n(n-1)/2
6for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) work();
7// 3: halving                           O(log n)
8for (int m = n; m > 1; m /= 2) work();
9// 4: doubling                          O(log n)
10for (int i = 1; i < n; i *= 2) work();
11// 5: linear outer, doubling inner      O(n log n)
12for (int i = 0; i < n; i++) for (int j = 1; j < n; j *= 2) work();
13// 6: two pointers                      O(n) even with a while inside a for
14int j = 0; for (int i = 0; i < n; i++) { while (j < n && cond(i, j)) { work(); j++; } }

Live state

0 work() calls

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 74 steps
StepLineStateWhat happens
1L3n=8Count how many times work() runs for n = 8. Complexity is just this count as a function of n.
2L4i=0Outer i = 0: start the inner loop.
3L4i=0 j=0 work() calls=1(i, j) = (0, 0): n calls for each of the n outer steps.
4L4i=0 j=1 work() calls=2(i, j) = (0, 1): n calls for each of the n outer steps.
5L4i=0 j=2 work() calls=3(i, j) = (0, 2): n calls for each of the n outer steps.
6L4i=0 j=3 work() calls=4(i, j) = (0, 3): n calls for each of the n outer steps.
7L4i=0 j=4 work() calls=5(i, j) = (0, 4): n calls for each of the n outer steps.
8L4i=0 j=5 work() calls=6(i, j) = (0, 5): n calls for each of the n outer steps.
9L4i=0 j=6 work() calls=7(i, j) = (0, 6): n calls for each of the n outer steps.
10L4i=0 j=7 work() calls=8(i, j) = (0, 7): n calls for each of the n outer steps.
11L4i=1Outer i = 1: start the inner loop.
12L4i=1 j=0 work() calls=9(i, j) = (1, 0): n calls for each of the n outer steps.
13L4i=1 j=1 work() calls=10(i, j) = (1, 1): n calls for each of the n outer steps.
14L4i=1 j=2 work() calls=11(i, j) = (1, 2): n calls for each of the n outer steps.
15L4i=1 j=3 work() calls=12(i, j) = (1, 3): n calls for each of the n outer steps.
16L4i=1 j=4 work() calls=13(i, j) = (1, 4): n calls for each of the n outer steps.
17L4i=1 j=5 work() calls=14(i, j) = (1, 5): n calls for each of the n outer steps.
18L4i=1 j=6 work() calls=15(i, j) = (1, 6): n calls for each of the n outer steps.
19L4i=1 j=7 work() calls=16(i, j) = (1, 7): n calls for each of the n outer steps.
20L4i=2Outer i = 2: start the inner loop.
21L4i=2 j=0 work() calls=17(i, j) = (2, 0): n calls for each of the n outer steps.
22L4i=2 j=1 work() calls=18(i, j) = (2, 1): n calls for each of the n outer steps.
23L4i=2 j=2 work() calls=19(i, j) = (2, 2): n calls for each of the n outer steps.
24L4i=2 j=3 work() calls=20(i, j) = (2, 3): n calls for each of the n outer steps.
25L4i=2 j=4 work() calls=21(i, j) = (2, 4): n calls for each of the n outer steps.
26L4i=2 j=5 work() calls=22(i, j) = (2, 5): n calls for each of the n outer steps.
27L4i=2 j=6 work() calls=23(i, j) = (2, 6): n calls for each of the n outer steps.
28L4i=2 j=7 work() calls=24(i, j) = (2, 7): n calls for each of the n outer steps.
29L4i=3Outer i = 3: start the inner loop.
30L4i=3 j=0 work() calls=25(i, j) = (3, 0): n calls for each of the n outer steps.
31L4i=3 j=1 work() calls=26(i, j) = (3, 1): n calls for each of the n outer steps.
32L4i=3 j=2 work() calls=27(i, j) = (3, 2): n calls for each of the n outer steps.
33L4i=3 j=3 work() calls=28(i, j) = (3, 3): n calls for each of the n outer steps.
34L4i=3 j=4 work() calls=29(i, j) = (3, 4): n calls for each of the n outer steps.
35L4i=3 j=5 work() calls=30(i, j) = (3, 5): n calls for each of the n outer steps.
36L4i=3 j=6 work() calls=31(i, j) = (3, 6): n calls for each of the n outer steps.
37L4i=3 j=7 work() calls=32(i, j) = (3, 7): n calls for each of the n outer steps.
38L4i=4Outer i = 4: start the inner loop.
39L4i=4 j=0 work() calls=33(i, j) = (4, 0): n calls for each of the n outer steps.
40L4i=4 j=1 work() calls=34(i, j) = (4, 1): n calls for each of the n outer steps.
41L4i=4 j=2 work() calls=35(i, j) = (4, 2): n calls for each of the n outer steps.
42L4i=4 j=3 work() calls=36(i, j) = (4, 3): n calls for each of the n outer steps.
43L4i=4 j=4 work() calls=37(i, j) = (4, 4): n calls for each of the n outer steps.
44L4i=4 j=5 work() calls=38(i, j) = (4, 5): n calls for each of the n outer steps.
45L4i=4 j=6 work() calls=39(i, j) = (4, 6): n calls for each of the n outer steps.
46L4i=4 j=7 work() calls=40(i, j) = (4, 7): n calls for each of the n outer steps.
47L4i=5Outer i = 5: start the inner loop.
48L4i=5 j=0 work() calls=41(i, j) = (5, 0): n calls for each of the n outer steps.
49L4i=5 j=1 work() calls=42(i, j) = (5, 1): n calls for each of the n outer steps.
50L4i=5 j=2 work() calls=43(i, j) = (5, 2): n calls for each of the n outer steps.
51L4i=5 j=3 work() calls=44(i, j) = (5, 3): n calls for each of the n outer steps.
52L4i=5 j=4 work() calls=45(i, j) = (5, 4): n calls for each of the n outer steps.
53L4i=5 j=5 work() calls=46(i, j) = (5, 5): n calls for each of the n outer steps.
54L4i=5 j=6 work() calls=47(i, j) = (5, 6): n calls for each of the n outer steps.
55L4i=5 j=7 work() calls=48(i, j) = (5, 7): n calls for each of the n outer steps.
56L4i=6Outer i = 6: start the inner loop.
57L4i=6 j=0 work() calls=49(i, j) = (6, 0): n calls for each of the n outer steps.
58L4i=6 j=1 work() calls=50(i, j) = (6, 1): n calls for each of the n outer steps.
59L4i=6 j=2 work() calls=51(i, j) = (6, 2): n calls for each of the n outer steps.
60L4i=6 j=3 work() calls=52(i, j) = (6, 3): n calls for each of the n outer steps.
61L4i=6 j=4 work() calls=53(i, j) = (6, 4): n calls for each of the n outer steps.
62L4i=6 j=5 work() calls=54(i, j) = (6, 5): n calls for each of the n outer steps.
63L4i=6 j=6 work() calls=55(i, j) = (6, 6): n calls for each of the n outer steps.
64L4i=6 j=7 work() calls=56(i, j) = (6, 7): n calls for each of the n outer steps.
65L4i=7Outer i = 7: start the inner loop.
66L4i=7 j=0 work() calls=57(i, j) = (7, 0): n calls for each of the n outer steps.
67L4i=7 j=1 work() calls=58(i, j) = (7, 1): n calls for each of the n outer steps.
68L4i=7 j=2 work() calls=59(i, j) = (7, 2): n calls for each of the n outer steps.
69L4i=7 j=3 work() calls=60(i, j) = (7, 3): n calls for each of the n outer steps.
70L4i=7 j=4 work() calls=61(i, j) = (7, 4): n calls for each of the n outer steps.
71L4i=7 j=5 work() calls=62(i, j) = (7, 5): n calls for each of the n outer steps.
72L4i=7 j=6 work() calls=63(i, j) = (7, 6): n calls for each of the n outer steps.
73L4i=7 j=7 work() calls=64(i, j) = (7, 7): n calls for each of the n outer steps.
74L4n=8 calls=64 return=64work() ran 64 times for n = 8: n². Growth class: O(n²). Change n and watch how the count scales.
4.03.7

Two-pointer amortized loops

A loop containing an inner while is not automatically quadratic. If each pointer only moves forward and never goes back, the total number of pointer moves is at most 2n, so the whole loop is O(n). This is amortised analysis of a loop.

Run the two-pointer pair search: the left and right pointers move toward each other, and together make at most n moves.

Java
1int l = 0, r = a.length - 1;           // sorted array
2while (l < r) {                        // each iteration moves l right or r left
3    int s = a[l] + a[r];
4    if (s == target) return new int[]{l, r};
5    if (s < target) l++; else r--;
6}                                      // at most n - 1 iterations: O(n)

Two-sum on a sorted array (opposite ends)

Interactive · edit the input

Your input

Try

int[] arr · length 8

1
3
4
6
8
11
14
17
01234567
Being comparedRuled outMatch / answer
Setup

Start with the smallest and largest values. Every step rules out one value for good.

Step 1 / 15
Java
1public static int[] twoSum(int[] arr, int target) {     // arr is sorted
2    int lo = 0, hi = arr.length - 1;
3    while (lo < hi) {
4        int sum = arr[lo] + arr[hi];
5        if (sum == target) return new int[] { lo, hi };
6        if (sum < target) lo++;          // need a bigger sum
7        else hi--;                       // need a smaller sum
8    }
9    return new int[] { -1, -1 };
10}

Live state

0 checks

target

19

lo

0

hi

7

No condition evaluated on this step
Execution trace (dry run table)Show 15 steps
StepLineStateWhat happens
1L2target=19 lo=0 hi=7Start with the smallest and largest values. Every step rules out one value for good.
2L5target=19 lo=0 hi=7 sum=1818 is too small. arr[lo] plus even the largest remaining value is too small, so arr[lo] can never be part of an answer.
3L6target=19 lo=1 hi=7lo = 1.
4L5target=19 lo=1 hi=7 sum=2020 is too large. arr[hi] plus even the smallest remaining value is too large, so arr[hi] is ruled out.
5L7target=19 lo=1 hi=6hi = 6.
6L5target=19 lo=1 hi=6 sum=1717 is too small. arr[lo] plus even the largest remaining value is too small, so arr[lo] can never be part of an answer.
7L6target=19 lo=2 hi=6lo = 2.
8L5target=19 lo=2 hi=6 sum=1818 is too small. arr[lo] plus even the largest remaining value is too small, so arr[lo] can never be part of an answer.
9L6target=19 lo=3 hi=6lo = 3.
10L5target=19 lo=3 hi=6 sum=2020 is too large. arr[hi] plus even the smallest remaining value is too large, so arr[hi] is ruled out.
11L7target=19 lo=3 hi=5hi = 5.
12L5target=19 lo=3 hi=5 sum=1717 is too small. arr[lo] plus even the largest remaining value is too small, so arr[lo] can never be part of an answer.
13L6target=19 lo=4 hi=5lo = 4.
14L5target=19 lo=4 hi=5 sum=19Found the pair.
15L5target=19 return=[4, 5]return [4, 5] after 7 checks. O(n) time, O(1) space.

Practice ladder

Now try it yourself

Easy

  • Count the iterations of for (i = 0; i < n; i += 2)
  • Count the iterations of for (i = 1; i < n; i *= 3)

Medium

  • Give the exact count for the triangular nest for i in 1..n, for j in i..n
  • Explain why a sliding window with an inner while-loop is O(n)

Advanced

  • Analyse for (i = 1; i <= n; i *= 2) for (j = 0; j < i; j++) and show it is O(n)

Key takeaways

  • Multiply nested counts, add sequential ones, sum dependent ones.
  • Doubling and halving counters give log n; a triangular nest gives n²/2.
  • Pointers that never move back make an inner loop amortised linear.