15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
The time complexity of loops comes from counting body executions. A loop that steps by 1 runs n times. Loops one after another add their counts, and an independent nested loop multiplies them: 4 times 4 is 16 for n = 4. A loop that doubles its variable runs about log n times.
| Single loop, step 1 | n body runs, Theta(n) |
|---|---|
| Sequential loops | n + n = 2n, Theta(n) |
| Nested, independent bounds | n x n = n^2, so 16 at n = 4, Theta(n^2) |
| Doubling loop | Smallest k with 2^k >= n; 4 runs at n = 16 (1, 2, 4, 8) |
| Auxiliary space | Theta(1): count, i and j are reused, not stacked |
| Inner bound depends on i | Do not multiply; count the real inner iterations |
Use these earlier ideas:
O, Ω, and Θ describe how work grows as n grows.Count how many times loop bodies execute.
Use these questions during the analysis:
1, or does it multiply or divide each time?Source material for the analysis approach:
Use n = 4.
Count every ordered pair visited by two independent nested loops:
1count = 0
2
3for i from 0 while i < n:
4 for j from 0 while j < n:
5 count = count + 1An ordered pair is written (i, j). Order matters: (0, 1) and (1, 0) are different pairs.
Before either loop runs:
| Value | State |
|---|---|
n | 4 |
i | 0 |
j | 0 |
count | 0 |
| Processed pairs | none |
The outer loop selects a row through i. The inner loop visits every column through j.
For i = 0, the inner loop visits:
1(0, 0), (0, 1), (0, 2), (0, 3)For i = 1, it initializes j to 0 and visits:
1(1, 0), (1, 1), (1, 2), (1, 3)The inner loop initializes j for each outer-loop value, so it completes every row.
Start with count = 0.
Nested loops with n = 4: the outer loop picks a row i, the inner loop visits all 4 columns j, and j starts over for every row. Every ordered pair is counted once, so count = 4 × 4 = 16.
1n = 4
2i = 0
3j = 0
4count = 0
5processed pairs = noneNo outer-loop row has been completed.
i = 0The inner loop processes:
1j = 0: process (0, 0), count becomes 1
2j = 1: process (0, 1), count becomes 2
3j = 2: process (0, 2), count becomes 3
4j = 3: process (0, 3), count becomes 4The inner condition fails at j = 4.
1i = 0 completed
2count = 4
3processed pairs = (0,0), (0,1), (0,2), (0,3)i = 1The inner loop resets j to 0.
1j = 0: process (1, 0), count becomes 5
2j = 1: process (1, 1), count becomes 6
3j = 2: process (1, 2), count becomes 7
4j = 3: process (1, 3), count becomes 81i = 1 completed
2count = 8
3processed pairs = every pair in rows 0 and 1i = 21j = 0: process (2, 0), count becomes 9
2j = 1: process (2, 1), count becomes 10
3j = 2: process (2, 2), count becomes 11
4j = 3: process (2, 3), count becomes 121i = 2 completed
2count = 12
3processed pairs = every pair in rows 0, 1, and 2i = 31j = 0: process (3, 0), count becomes 13
2j = 1: process (3, 1), count becomes 14
3j = 2: process (3, 2), count becomes 15
4j = 3: process (3, 3), count becomes 16Now i advances to 4. The outer condition i < n is false because 4 < 4 is false.
1count = 16
2processed pairs = all pairs (i, j) where 0 <= i < 4 and 0 <= j < 4
3loops endAt the start of the outer iteration for a particular i:
n pairs.count equals the number of completed rows times n.The loop invariant is:
At the start of outer iteration
i,count = i × n, and every pair(a, b)with0 <= a < iand0 <= b < nhas been processed exactly once.
For n = 4:
| Start of outer iteration | i | Completed rows | Expected count |
|---|---|---|---|
| First | 0 | 0 | 0 × 4 = 0 |
| Second | 1 | 1 | 1 × 4 = 4 |
| Third | 2 | 2 | 2 × 4 = 8 |
| Fourth | 3 | 3 | 3 × 4 = 12 |
When the inner loop finishes one row, it processes exactly the pairs whose first coordinate is the current i. It adds n to count, preparing the invariant for the next outer value.
Consider:
1i = 0
2while i < n:
3 do one constant-time body operation
4 i = i + 1The index values that enter the body are:
10, 1, 2, ..., n - 1There are n such values. The body executes exactly n times.
Place two independent n-iteration loops one after the other:
1for i from 0 while i < n:
2 do one operation
3
4for j from 0 while j < n:
5 do one operationThe first body runs n times. The second body runs n times.
1total body executions = n + n = 2nThe exact count is 2n, so the time class is Θ(n).
The example has one inner loop inside each outer-loop iteration:
1for i from 0 while i < n:
2 for j from 0 while j < n:
3 count = count + 1The outer loop runs n times.
For every fixed i, the inner loop starts j at 0 and runs while j < n. The inner body runs n times for each outer iteration.
1total body executions = n × n = n²Multiplication applies because the inner bound is independent of i.
When the inner bound depends on the outer index, count the actual number of inner iterations. An inner loop with condition j < i does not run n times for every outer value.
Consider a loop beginning at 1:
1i = 1
2while i < n:
3 do one operation
4 i = 2 × iAfter k updates, the loop variable is 2^k.
The loop stops once:
12^k >= nFor n >= 1, the number of body executions is the smallest integer k for which 2^k >= n. The count is proportional to log n.
For n = 16, the body sees:
1i = 1, 2, 4, 8It runs 4 times. The update produces 16, and then 16 < 16 is false.
A variable divided by 2 each iteration also reaches its stopping boundary after logarithmically many updates. Repeated factor-of-two changes determine the iteration count.
The first procedure counts the ordered pairs visited by the nested loops.
Input: nonnegative integer n
Return value: number of ordered pairs (i, j) visited with 0 <= i < n and 0 <= j < n
Mutation behavior: does not mutate n or any caller-owned structure
Boundary: when n = 0, returns 0
101 procedure pairCount(n):
202 count = 0
303 i = 0
404 while i < n:
505 j = 0
606 while j < n:
707 count = count + 1
808 j = j + 1
909 i = i + 1
1010 return countThe second procedure counts iterations in a doubling loop.
Input: integer n >= 1
Return value: number of values beginning at 1 that are processed while the value is less than n
Mutation behavior: does not mutate n
Boundary: when n = 1, returns 0
101 procedure doublingSteps(n):
202 steps = 0
303 value = 1
404 while value < n:
505 steps = steps + 1
606 value = 2 × value
707 return stepsThe doublingSteps contract counts body executions. It does not count the final value that reaches or passes n.
Dry-run pairCount(4).
| Line | Action | i | j | count |
|---|---|---|---|---|
| 2 | Set count = 0 | — | — | 0 |
| 3 | Set i = 0 | 0 | — | 0 |
| 4 | Check 0 < 4; enter outer loop | 0 | — | 0 |
| 5 | Set j = 0 | 0 | 0 | 0 |
| 6 | Check 0 < 4; enter inner loop | 0 | 0 | 0 |
| 7 | Process (0, 0) | 0 | 0 | 1 |
| 8 | Set j = 1 | 0 | 1 | 1 |
| 6 | Check 1 < 4; enter inner loop | 0 | 1 | 1 |
| 7 | Process (0, 1) | 0 | 1 | 2 |
| 8 | Set j = 2 | 0 | 2 | 2 |
| 6 | Check 2 < 4; enter inner loop | 0 | 2 | 2 |
| 7 | Process (0, 2) | 0 | 2 | 3 |
| 8 | Set j = 3 | 0 | 3 | 3 |
| 6 | Check 3 < 4; enter inner loop | 0 | 3 | 3 |
| 7 | Process (0, 3) | 0 | 3 | 4 |
| 8 | Set j = 4 | 0 | 4 | 4 |
| 6 | Check 4 < 4; leave inner loop | 0 | 4 | 4 |
| 9 | Set i = 1 | 1 | 4 | 4 |
State 1 is complete: the first row has four pairs.
The remaining outer iterations have these inner-loop states:
| Completed outer value | Pairs added in that row | count after line 9 |
|---|---|---|
i = 1 | (1,0), (1,1), (1,2), (1,3) | 8 |
i = 2 | (2,0), (2,1), (2,2), (2,3) | 12 |
i = 3 | (3,0), (3,1), (3,2), (3,3) | 16 |
After processing (3, 3):
| Line | Action | i | j | count |
|---|---|---|---|---|
| 8 | Set j = 4 | 3 | 4 | 16 |
| 6 | Check 4 < 4; leave inner loop | 3 | 4 | 16 |
| 9 | Set i = 4 | 4 | 4 | 16 |
| 4 | Check 4 < 4; leave outer loop | 4 | 4 | 16 |
| 10 | Return count | 4 | 4 | 16 |
pairCount(4) returns 16.
We show that pairCount(n) returns the number of ordered pairs in the n by n grid.
Before the first outer-loop iteration, line 2 sets:
1count = 0Line 3 sets:
1i = 0There are no pairs (a, b) with 0 <= a < 0, so no pairs should have been processed. Also:
1count = 0 = 0 × nThe invariant holds before the first outer iteration.
Assume the invariant holds at the start of an outer iteration with index i.
The invariant says that all rows before i have been processed exactly once, and:
1count = i × nLine 5 sets j = 0. The inner loop runs while j < n, so it uses exactly these values:
10, 1, 2, ..., n - 1For this fixed i, the inner loop processes each pair:
1(i, 0), (i, 1), ..., (i, n - 1)exactly once. It neither skips a j value nor repeats one because j starts at 0 and increases by exactly 1.
The inner loop adds 1 to count exactly n times. Therefore:
1new count = i × n + n
2 = (i + 1) × nLine 9 advances i to i + 1. At the next outer iteration, all rows before the new i have been processed exactly once, and count has the required value. The invariant is preserved.
The outer loop uses:
1i = 0, 1, 2, ..., n - 1It terminates when i = n.
At that moment, the invariant says every pair (a, b) satisfying:
10 <= a < n
20 <= b < nhas been processed exactly once. It also says:
1count = n × n = n²Therefore, pairCount(n) returns the number of ordered pairs in the n by n grid.
For n = 4:
1count = 4 × 4 = 16The result matches the worked trace.
pairCount(n)Start with the body on line 7:
1count = count + 1The outer loop has n iterations:
1i = 0, 1, ..., n - 1For each outer iteration, the inner loop has n iterations:
1j = 0, 1, ..., n - 1Therefore, line 7 executes:
1n × n = n²times.
The condition checks, index updates, and loop initialization also occur a number of times bounded by a constant multiple of n². They do not change the growth class.
1Time: Θ(n²)The procedure stores only:
1count, i, jThese are a constant number of scalar variables, regardless of n.
1Auxiliary space: Θ(1)The input integer and returned integer do not add growing storage structures.
Two separate loops with n body executions each perform:
1n + n = 2nbody executions.
1Time: Θ(n)doublingSteps(n)The processed values are:
11, 2, 4, 8, ...After k loop iterations:
1value = 2^kThe loop ends when:
12^k >= nSo k is proportional to log n.
1Time: Θ(log n)
2Auxiliary space: Θ(1)For the stated boundary n = 1, the first condition check is:
11 < 1The condition is false. The body runs zero times.
Incorrect assumption: “Two nested loops always mean 2n operations.”
Exposing input: n = 4
For the nested grid loops, this reasoning gives:
14 + 4 = 8The inner loop runs four times for each of the four outer iterations:
14 × 4 = 16Correction: multiply when an independent inner loop completes for every outer-loop iteration.
Incorrect assumption: “Any second loop makes the code O(n²).”
1for i from 0 while i < n:
2 do one operation
3
4for j from 0 while j < n:
5 do one operationExposing input: n = 4
The first loop performs 4 body executions. The second also performs 4.
14 + 4 = 8The count is 2n. The time is Θ(n).
Correction: sequential loops add their costs.
Incorrect assumption: “If the condition says i < 16, the loop runs 16 times.”
1i = 1
2while i < 16:
3 i = 2 × iExposing input: n = 16
The body values are:
11, 2, 4, 8The body runs 4 times. After the fourth update, i becomes 16, and the condition fails.
Correction: list the values or solve 2^k >= n. A doubling loop has logarithmically many iterations.
Incorrect assumption: “count = count + 1 runs n² times, so it uses O(n²) space.”
Exposing input: n = 4
The final count is 16. The algorithm repeatedly updates one scalar variable:
1countIt also stores i and j.
Correction: auxiliary space measures storage held at one time. pairCount(n) uses Θ(1) auxiliary space.
| Input | Expected pairCount(n) result | Reason |
|---|---|---|
0 | 0 | The outer condition 0 < 0 is false. |
1 | 1 | Only (0, 0) is processed. |
4 | 16 | Four rows, each with four pairs. |
For doublingSteps(n) with the stated n >= 1 contract:
| Input | Processed values | Expected result |
|---|---|---|
1 | none | 0 |
2 | 1 | 1 |
8 | 1, 2, 4 | 3 |
16 | 1, 2, 4, 8 | 4 |
Implement these two procedures:
pairCount(n) uses nested loops and returns the number of ordered pairs visited.doublingSteps(n) starts at 1, repeatedly doubles while the value is less than n, and returns the number of body iterations.The executable tests verify this contract:
1pairCount(0) = 0
2pairCount(1) = 1
3pairCount(4) = 16
4
5doublingSteps(1) = 0
6doublingSteps(2) = 1
7doublingSteps(8) = 3
8doublingSteps(16) = 41def pair_count(n):
2 count = 0
3 i = 0
4 while i < n:
5 j = 0 # the inner index restarts for every i
6 while j < n:
7 count += 1
8 j += 1
9 i += 1
10 return count
11
12def doubling_steps(n):
13 steps = 0
14 value = 1
15 while value < n:
16 steps += 1
17 value *= 2
18 return steps
19
20for n in [0, 1, 4]:
21 print(f"pairCount({n}) = {pair_count(n)}")
22for n in [1, 2, 8, 16]:
23 print(f"doublingSteps({n}) = {doubling_steps(n)}")1public class Main {
2 static int pairCount(int n) {
3 int count = 0;
4 int i = 0;
5 while (i < n) {
6 int j = 0; // the inner index restarts for every i
7 while (j < n) {
8 count++;
9 j++;
10 }
11 i++;
12 }
13 return count;
14 }
15
16 static int doublingSteps(int n) {
17 int steps = 0;
18 int value = 1;
19 while (value < n) {
20 steps++;
21 value *= 2;
22 }
23 return steps;
24 }
25
26 public static void main(String[] args) {
27 for (int n : new int[]{0, 1, 4}) {
28 System.out.println("pairCount(" + n + ") = " + pairCount(n));
29 }
30 for (int n : new int[]{1, 2, 8, 16}) {
31 System.out.println("doublingSteps(" + n + ") = " + doublingSteps(n));
32 }
33 }
34}1#include <iostream>
2using namespace std;
3
4int pairCount(int n) {
5 int count = 0;
6 int i = 0;
7 while (i < n) {
8 int j = 0; // the inner index restarts for every i
9 while (j < n) {
10 count++;
11 j++;
12 }
13 i++;
14 }
15 return count;
16}
17
18int doublingSteps(int n) {
19 int steps = 0;
20 int value = 1;
21 while (value < n) {
22 steps++;
23 value *= 2;
24 }
25 return steps;
26}
27
28int main() {
29 for (int n : {0, 1, 4}) cout << "pairCount(" << n << ") = " << pairCount(n) << endl;
30 for (int n : {1, 2, 8, 16}) cout << "doublingSteps(" << n << ") = " << doublingSteps(n) << endl;
31}1function pairCount(n) {
2 let count = 0;
3 let i = 0;
4 while (i < n) {
5 let j = 0; // the inner index restarts for every i
6 while (j < n) {
7 count++;
8 j++;
9 }
10 i++;
11 }
12 return count;
13}
14
15function doublingSteps(n) {
16 let steps = 0;
17 let value = 1;
18 while (value < n) {
19 steps++;
20 value *= 2;
21 }
22 return steps;
23}
24
25for (const n of [0, 1, 4]) console.log(`pairCount(${n}) = ${pairCount(n)}`);
26for (const n of [1, 2, 8, 16]) console.log(`doublingSteps(${n}) = ${doublingSteps(n)}`);It depends on how many values the index takes. Step by 1 up to n gives O(n). Multiply or divide the index by 2 each pass and it gives O(log n). A fixed number of passes gives O(1).
Only when the number of iterations does not depend on n. The loop while i < n with i = i + 1 runs n times, so it is O(n), however simple the body is.
O(1) grows slower: the count never changes with n. O(log n) grows slowly, with 4 steps at n = 16 and 3 at n = 8. Both are cheap; the constant factor decides small cases.
Either works. Count how many values the index takes, not where it starts. Running i from 0 while i < n and from 1 while i <= n both give n iterations.
Do not multiply by n. Count the real inner iterations. With j < i the total is 0 + 1 + ... + (n - 1) = n(n - 1) / 2, which is still Theta(n^2).