There are some tricks for figuring out Big-O notation by just looking at the loop, but it there is less opportunity for error when using the sum of the loop’s series to find its Big-O. I realized that the Big-O is best calculated this way when when I first saw this problem online:
int fun(int n) {int count = 0;for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++) count += 1; return count;}
The Big-O of this problem is O(n), but when I first looked at it, I thought it was O(n log n). Using the equation arithmetic and geometric series will guarantee the correct Big-O notation is found.
This method has three steps:
- Find the loop’s series by plotting some of its executions.
- Use a series formula to find the total executions.
- Big lower-order terms and constants to get its Big-O notation.
Skip to example 1 to see the example above solved. Keep reading if you want to start at the beginning of series and their relationship to loops.
All logs are base-2. Language is c++ but answers apply to Big-O in any language.
Series refresher
If, like me, you haven’t looked at series since high school algebra:
A sequence is an ordered list of sequential terms. A series is the sum of the sequence. They can be arithmetic or geometric.
Arithmetic: the terms differ by the same constant (1, 3, 5, 7…)
Geometric: the terms differ by the same ratio (2, 4, 8, 16…)
Sum of series formulas:
Nested loops can always be assessed as a series. This allows us to find the entire loops’ amount of iterations at once.
(Technically a single loop can also be assessed this way, as we’ll see, but it doesn’t make a lot of sense.)
The number of terms, n, is the amount of times the outer loop turns.
This is the variable in the series’ equation since the order of growth is factor of the input. The value of n is the number of iterations within each turn.
Imagine a single loop like:
int count = 0;for(int i; i < 3; i++) {
count++;
}
The entire loop turns three times: __ + __ + __
executing the body one time each: 1 + 1 + 1 = 3
If that was a nested loop:
int count = 0;for(int i; i < 3; i++) { for(int j; j < 3; j++) {
count++;
}
}
The entire loop still turns three times, but within each execution there are three additional executions of the body: 3 + 3 + 3 = 9
Finally, if it was loop with two loops inside (triple loop):
int count = 0;for(int i; i < 3; i++) { for(int j; j < 3; j++) { for(int k; k < 3; k++) {
count++;
}
}
}
The entire loop still turns three times, but within each turn there are three additional executions of the body, and within each of those turns are three more executions: 3*3 + 3*3 + 3*3 = 27
Say if instead of incrementing to i > 3 , there was a variable n:
int count = 0;for(int i; i < n; i++) { for(int j; j < n; j++) { for(int k; k < n; k++) {
count++;
}
}
}
If this was a series, it would be: n*n + n*n + n*n … n times.
This is an arithmetic series with a difference of 0 or a geometric series with a ratio of 1. Either works, but plugged into the arithmetic series formula, it is:
The big-O notation of n³ is O(n³).
This is a pretty easy Big-O problem to understand by looking at, but it helps show that ALL loops, including single loops, are technically a series.
Example 1
Given the loop first mentioned above:
int count = 0;for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++)
count += 1;
From looking at the loops, it might seem like the intuitive answer is O(n log n). The first loop seems like O(log) and the second seems O(n) and you can multiply them to get O(n log n). This is not correct, since this doesn’t consider is that the second loop is not a straightforward linear loop.
Imagine this question was about the single outer loop:
for (int i = n; i > 0; i /= 2) The relationship between n and the number of turns is logarithmic. Given i = n, this loop is divides i by 2 each turn, returning about how many times n is divisible by 2. In other words, x so 2ˣ = n.
Written out, Say n = 16.
i = 16
i = 8
i = 4
i = 2
i = 1 (after this, i = 0 , and the loop stops)
If just the outer loop were present, this would run 5 times.
1 + 1 + 1 + 1 + 1 = 5
You might be thinking that log₂ 16 = 4, not 5. So is the relationship really logarithmic? If you did more of these out, a general pattern would emerge, where the number of iterations would always be ⌈log n⌉ or log n + 1.
Since lower-order terms are dropped for Big-O, this loops’ big-O notation is O(log n). More important than plotting the exact number of iterations, is the relationship between the input n and the number of iterations, which is logarithmic due the fact mentioned above that i is halved on each iteration, roughly looping x times where x satisfies 2ˣ = n.
Now adding back in the inner loop:
int count = 0;for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
Continuing with n = 16.
i = 16, j runs 16 times.
i = 8, j runs 8 times
i = 4, j runs 4 times
i = 2, j runs 2 times
i = 1, j runs 1 time
16 + 8 + 4 + 2 + 1 = 31
We need to generalize the series above, since the runtime needs to apply to all n. Generalizing the series above gets:
i = n, j runs n times.
i = n/2, j runs n/2 times
i = n/4, j runs n/4 times
…i = 1, j runs 1 time
n + n/2 + n/4 + … 1, for log n terms
It’s evident this is a geometric series since there’s a common ratio 1/2 between all terms. Applying the formula above:
a = 16 (first term can be an arbitrary integer)
r = 1/2 (ratio between terms)
n= log(n) (number of terms—remember we found this above when looking at the outer loop)
To find order of growth, drop the coefficients and lower-order terms.
= O(n)
Therefore, it is linear.
Example 2
This another problem that is hard to “eyeball” for Big-O but is solved with a series.
for (int i = 1; i <= n; i *= 2) {
j = i;
while (j > 1) {
j /= 2;
}
}For the outer loop, i is doubled on each iteration. i is 2 raised to the number of iterations (2⁰ = 1, 2¹ = 2, 2² = 4, 2³ = 8). Same as before, this is logarithmic, since the number of iterations roughly equals x times where x satisfies 2ˣ = n.
The outer loop therefore iterates log n times: _ _ _ _ … log n
The inner loop iterates while j is greater than 1. j doubles each iteration of i. Every time j doubles, it will take exactly one more iteration of j to divide it by 2 so j / 2 = 0.
Taken to the conclusion, when i = n, j will iterate log n times, since (as we’ve shown) the question how many times can n be divided by 2 before n = 0? is the same as asking 2ˣ = n?
i = 1, j runs 0 times
i = 2, j runs 1 time
i = 4, j runs 2 times
i = 8 , j runs 3 times
… i = n, j runs log n times
0 + 1 + 2 + 3 … log n, for log n terms.
This is an arithmetic series, it can be expressed as:
Without even simplifying the entire thing, it’s clear that the highest-order term will be log²n, as we can drop the 0 and the 1/2.
O(log² n)
I like this method since:
- You don’t even need to complete the entire equation to the exact right answer. Just enough to get the highest-order term.
- It takes into account the entire loop. No multiplying the inner and outer loops.
While it has a few extra steps, it reduces potential errors from eyeballing loops to figure out their Big-O.
