Big O Notation: How Running Time Grows
When n doubles
Does a list hold the same value twice? Here are three answers that all work: check every pair, sort a copy and compare neighbours, or remember each value in a set as you go. On 1,000 values all three finish before you can blink. Hand them four times as many and they stop looking alike: on our judge the Python pair check went from 37 ms to 0.59 s, 16 times slower, while the set, given 40,000 values, finished in 5 ms.
Big O notation names that difference: how the work grows when the input grows. It doesn't say how many seconds a program takes, because that depends on the machine. It says what happens to the time when n doubles, and you can read it off the code before you run anything.
This lesson shows how: count the steps that grow with n, keep the part that grows fastest, and know which growth fits in a second. Then the loops that fool people, the library calls that hide a loop, the memory a program needs, and what Big O leaves out.
Three ways to find a repeat
Here are all three, each timed on n different values (no repeat, so none of them can stop early), then on 2n and 4n, keeping the fastest of five runs after a warm-up on the biggest input. Each prints its three times and how much each doubling multiplied them:
#include <bits/stdc++.h>
using namespace std;
bool hasDuplicatePairs(const vector<int>& nums) { // compares every pair once
for (size_t i = 0; i < nums.size(); i++)
for (size_t j = i + 1; j < nums.size(); j++)
if (nums[i] == nums[j]) return true;
return false;
}
bool hasDuplicateSorted(const vector<int>& nums) { // sorts a copy, then compares neighbours
vector<int> ordered = nums;
sort(ordered.begin(), ordered.end());
for (size_t i = 1; i < ordered.size(); i++)
if (ordered[i] == ordered[i - 1]) return true;
return false;
}
bool hasDuplicateSet(const vector<int>& nums) { // remembers every value it has seen
unordered_set<int> seen;
for (int x : nums) {
if (seen.count(x)) return true;
seen.insert(x);
}
return false;
}
mt19937 rng(1);
vector<int> distinct(int n) { // n different values, so no check stops early
vector<int> nums(n);
iota(nums.begin(), nums.end(), 0);
shuffle(nums.begin(), nums.end(), rng);
return nums;
}
double seconds(bool (*check)(const vector<int>&), const vector<int>& nums) { // the fastest of five runs
double best = 1e9;
for (int run = 0; run < 5; run++) {
auto start = chrono::steady_clock::now();
if (check(nums)) puts("found one");
best = min(best, chrono::duration<double>(chrono::steady_clock::now() - start).count());
}
return best;
}
int main() {
pair<const char*, bool (*)(const vector<int>&)> checks[] = {
{"hasDuplicatePairs", hasDuplicatePairs},
{"hasDuplicateSorted", hasDuplicateSorted},
{"hasDuplicateSet", hasDuplicateSet}};
int sizes[] = {10000, 20000, 20000};
for (int k = 0; k < 3; k++) {
auto [name, check] = checks[k];
int n = sizes[k];
vector<int> biggest = distinct(4 * n);
for (int w = 0; w < 3; w++) check(biggest); // warm up on the biggest input first
double t1 = seconds(check, distinct(n)), t2 = seconds(check, distinct(2 * n)),
t4 = seconds(check, distinct(4 * n));
printf("%s: %.4fs %.4fs %.4fs (x%.1f, x%.1f)\n", name, t1, t2, t4, t2 / t1, t4 / t2);
}
}
// hasDuplicatePairs: 0.0165s 0.0655s 0.2613s (x4.0, x4.0)
// hasDuplicateSorted: 0.0011s 0.0023s 0.0050s (x2.1, x2.1)
// hasDuplicateSet: 0.0017s 0.0035s 0.0079s (x2.1, x2.2)import random
import time
def has_duplicate_pairs(nums): # compares every pair once
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return True
return False
def has_duplicate_sorted(nums): # sorts a copy, then compares neighbours
ordered = sorted(nums)
for i in range(1, len(ordered)):
if ordered[i] == ordered[i - 1]:
return True
return False
def has_duplicate_set(nums): # remembers every value it has seen
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return False
def distinct(n): # n different values, so no check stops early
return random.sample(range(10 * n), n)
def seconds(check, nums): # the fastest of five runs
best = float("inf")
for _ in range(5):
start = time.perf_counter()
check(nums)
best = min(best, time.perf_counter() - start)
return best
for check, n in ((has_duplicate_pairs, 1000), (has_duplicate_sorted, 10000), (has_duplicate_set, 10000)):
biggest = distinct(4 * n)
for _ in range(3): # warm up on the biggest input first
check(biggest)
t1, t2, t4 = (seconds(check, distinct(size)) for size in (n, 2 * n, 4 * n))
print(f"{check.__name__}: {t1:.4f}s {t2:.4f}s {t4:.4f}s (x{t2 / t1:.1f}, x{t4 / t2:.1f})")
# has_duplicate_pairs: 0.0369s 0.1479s 0.5924s (x4.0, x4.0)
# has_duplicate_sorted: 0.0024s 0.0054s 0.0129s (x2.2, x2.4)
# has_duplicate_set: 0.0011s 0.0027s 0.0054s (x2.6, x2.0)import java.util.*;
import java.util.function.Predicate;
public class Main {
static boolean hasDuplicatePairs(int[] nums) { // compares every pair once
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] == nums[j]) return true;
return false;
}
static boolean hasDuplicateSorted(int[] nums) { // sorts a copy, then compares neighbours
int[] ordered = nums.clone();
Arrays.sort(ordered);
for (int i = 1; i < ordered.length; i++)
if (ordered[i] == ordered[i - 1]) return true;
return false;
}
static boolean hasDuplicateSet(int[] nums) { // remembers every value it has seen
Set<Integer> seen = new HashSet<>();
for (int x : nums) {
if (seen.contains(x)) return true;
seen.add(x);
}
return false;
}
static Random rng = new Random(1);
static int[] distinct(int n) { // n different values, so no check stops early
int[] nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = i;
for (int i = n - 1; i > 0; i--) {
int j = rng.nextInt(i + 1), t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
return nums;
}
static double seconds(Predicate<int[]> check, int[] nums) { // the fastest of five runs
double best = Double.MAX_VALUE;
for (int run = 0; run < 5; run++) {
long start = System.nanoTime();
if (check.test(nums)) System.out.println("found one");
best = Math.min(best, (System.nanoTime() - start) / 1e9);
}
return best;
}
public static void main(String[] args) {
String[] names = {"hasDuplicatePairs", "hasDuplicateSorted", "hasDuplicateSet"};
List<Predicate<int[]>> checks =
List.of(Main::hasDuplicatePairs, Main::hasDuplicateSorted, Main::hasDuplicateSet);
int[] sizes = {10000, 20000, 20000};
for (int k = 0; k < 3; k++) {
Predicate<int[]> check = checks.get(k);
int n = sizes[k];
int[] biggest = distinct(4 * n);
for (int w = 0; w < 3; w++) check.test(biggest); // warm up: Java compiles a method as it runs
double t1 = seconds(check, distinct(n)), t2 = seconds(check, distinct(2 * n)),
t4 = seconds(check, distinct(4 * n));
System.out.printf("%s: %.4fs %.4fs %.4fs (x%.1f, x%.1f)%n", names[k], t1, t2, t4, t2 / t1, t4 / t2);
}
}
}
// hasDuplicatePairs: 0.0110s 0.0432s 0.1794s (x3.9, x4.2)
// hasDuplicateSorted: 0.0034s 0.0073s 0.0013s (x2.2, x0.2)
// hasDuplicateSet: 0.0020s 0.0023s 0.0033s (x1.1, x1.4)function hasDuplicatePairs(nums) { // compares every pair once
for (let i = 0; i < nums.length; i++)
for (let j = i + 1; j < nums.length; j++)
if (nums[i] === nums[j]) return true;
return false;
}
function hasDuplicateSorted(nums) { // sorts a copy, then compares neighbours
const ordered = [...nums].sort((a, b) => a - b);
for (let i = 1; i < ordered.length; i++)
if (ordered[i] === ordered[i - 1]) return true;
return false;
}
function hasDuplicateSet(nums) { // remembers every value it has seen
const seen = new Set();
for (const x of nums) {
if (seen.has(x)) return true;
seen.add(x);
}
return false;
}
function distinct(n) { // n different values, so no check stops early
const nums = Array.from({ length: n }, (_, i) => i);
for (let i = n - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[nums[i], nums[j]] = [nums[j], nums[i]];
}
return nums;
}
function seconds(check, nums) { // the fastest of five runs
let best = Infinity;
for (let run = 0; run < 5; run++) {
const start = process.hrtime.bigint();
if (check(nums)) console.log("found one");
best = Math.min(best, Number(process.hrtime.bigint() - start) / 1e9);
}
return best;
}
for (const [check, n] of [[hasDuplicatePairs, 10000], [hasDuplicateSorted, 20000], [hasDuplicateSet, 20000]]) {
const biggest = distinct(4 * n);
for (let w = 0; w < 3; w++) check(biggest); // warm up on the biggest input first
const t1 = seconds(check, distinct(n)), t2 = seconds(check, distinct(2 * n)), t4 = seconds(check, distinct(4 * n));
console.log(`${check.name}: ${t1.toFixed(4)}s ${t2.toFixed(4)}s ${t4.toFixed(4)}s ` +
`(x${(t2 / t1).toFixed(1)}, x${(t4 / t2).toFixed(1)})`);
}
// hasDuplicatePairs: 0.0815s 0.3257s 1.3022s (x4.0, x4.0)
// hasDuplicateSorted: 0.0065s 0.0139s 0.0295s (x2.1, x2.1)
// hasDuplicateSet: 0.0019s 0.0040s 0.0090s (x2.1, x2.2)Each language starts where its runs are long enough to time: Python's pair check at 1,000 values and its sort and set at 10,000; the others' pair checks at 10,000 and their sorts and sets at 20,000. The ratios are what matter:
- Every pair went ×3.9 to ×4.2 each time n doubled. It compares each value with every later one, n(n − 1)/2 comparisons, and twice the values make four times the pairs.
- Sort, then neighbours went ×2.1 to ×2.4 in C++, Python and JavaScript: sorting n values takes about n log n steps, and the log n part grows by one step when n doubles.
- A set went ×2.0 to ×2.5 in those three: one look-up and one insert per value, n of each. Its times wobble more than the sort's, because a bigger set fits less well in the processor's fast memory.
Java's pair check went ×3.9 and ×4.2 like the others, but its sort and set times jumped (×2.1 then ×0.2, and ×1.1 then ×1.4). Its Arrays.sort on an int[] changes method as the array grows, and its set boxes every value into an object, so a run of a few milliseconds is mostly Java compiling code and cleaning up memory; at sizes big enough to swamp that, our judge ran out of memory. Timing shows the growth only when a run is long and steady. Counting steps, as the rest of this lesson does, always shows it.
Counting the steps. For the pair check, the step that grows is the comparison, and there are n(n − 1)/2 of them: 499,500 for n = 1,000. Big O keeps the term that grows fastest and drops its constant: n(n − 1)/2 = n²/2 − n/2, so the pair check is O(n²), said "order n squared". The sort is O(n log n) and the set is O(n).
- Constants go because they don't change the ratio: n²/2 and 5n² both go ×4 when n doubles. A faster machine changes the constant too, never the ratio.
- Smaller terms go because they stop mattering: at n = 100,000 the n/2 part is 0.001% of n²/2.
Predicting a run you haven't made. The ratio tells you what a bigger input will cost. The C++ pair check took 0.26 s on 40,000 values. The problem Contains Duplicate allows 100,000, 2.5 times as many, so it should take 2.5² = 6.25 times as long: about 1.6 s. It took 1.63 s. That is what Big O is for: before you run anything, it tells you the pair check needs over a second where the set needs a few milliseconds. The same sum for Python, from its 0.59 s on 4,000 values, says about 6 minutes for 100,000; we didn't wait. The Python set took 26 ms on 100,000 values.
What fits in a second
Each growth rate has a largest n it can handle in a second. We timed the simplest code of each kind on our judge, growing n (by a quarter, or by one for subsets and orderings) until one run took over a second: a loop that adds n numbers, a library sort of n numbers, the sum of every pair, of every triple and of every subset (two calls per value), and every ordering. The largest n that finished in a second:
| Growth | What we timed | C++ | Python |
|---|---|---|---|
| O(n) | a loop over n numbers | 646,234,393 | 13,552,421 |
| O(n log n) | sorting n numbers | 10,841,937 | 1,421,066 |
| O(n²) | every pair's sum | 44,370 | 3,618 |
| O(n³) | every triple's sum | 1,675 | 340 |
| O(2ⁿ) | every subset's sum | 28 | 21 |
| O(n!) | every ordering | 11 | 9 |
Each number holds for its own program on our judge, so read them as sizes, not exact limits; What Big O leaves out shows one loop running at two speeds in two builds. Java and JavaScript landed in the same range as C++: 69,327 and 28,397 for every pair, 1,340 each for every triple, 27 and 25 for subsets, 11 each for orderings. In a second C++ ran 48 times as many loop steps as Python, yet the gap in n shrinks as the growth gets steeper: one more value doubles the subsets in any language, so on that row the two differ by only 7.
Reading a problem's limits. The limit on n is a hint about the growth the problem expects. Real solutions do more per step than these loops, so leave room:
- n ≤ 10 or so: trying every ordering, O(n!), fits; tight in Python, which managed 9.
- n ≤ 20: every subset, O(2ⁿ).
- n ≤ 500: three nested loops, O(n³); tight in Python, which managed 340.
- n ≤ 5,000: two nested loops, O(n²); tight in Python, which managed 3,618.
- n ≤ 10⁶: O(n log n), a sort or a heap.
- n ≤ 10⁸: O(n) in C++, Java and JavaScript; Python manages about 10⁷.
- n up to 10¹⁸: O(log n) or O(√n) arithmetic. Halving 10¹⁸ reaches 1 in 59 steps.
So when a problem says n ≤ 10⁵, it is telling you that two nested loops over the input won't pass and a sort will.
Reading a loop
Count how many times the innermost line runs, as a sum over the loops around it. Each function below counts its steps and prints the count for n = 1,000, 2,000 and 4,000, so you can see the growth in the numbers.
One after another, or one inside another
long long twoLoops(int n) { // one loop after the other
long long count = 0;
for (int i = 0; i < n; i++) count++;
for (int j = 0; j < n; j++) count++;
return count;
}
long long fixedInner(int n) { // an inner loop of 100, whatever n is
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < 100; j++) count++;
return count;
}
long long everyPair(int n) { // an inner loop of n
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) count++;
return count;
}
// twoLoops [2000, 4000, 8000]
// fixedInner [100000, 200000, 400000]
// everyPair [1000000, 4000000, 16000000]def two_loops(n): # one loop after the other
count = 0
for i in range(n):
count += 1
for j in range(n):
count += 1
return count
def fixed_inner(n): # an inner loop of 100, whatever n is
count = 0
for i in range(n):
for j in range(100):
count += 1
return count
def every_pair(n): # an inner loop of n
count = 0
for i in range(n):
for j in range(n):
count += 1
return count
# two_loops [2000, 4000, 8000]
# fixed_inner [100000, 200000, 400000]
# every_pair [1000000, 4000000, 16000000]static long twoLoops(int n) { // one loop after the other
long count = 0;
for (int i = 0; i < n; i++) count++;
for (int j = 0; j < n; j++) count++;
return count;
}
static long fixedInner(int n) { // an inner loop of 100, whatever n is
long count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < 100; j++) count++;
return count;
}
static long everyPair(int n) { // an inner loop of n
long count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) count++;
return count;
}
// twoLoops [2000, 4000, 8000]
// fixedInner [100000, 200000, 400000]
// everyPair [1000000, 4000000, 16000000]function twoLoops(n) { // one loop after the other
let count = 0;
for (let i = 0; i < n; i++) count++;
for (let j = 0; j < n; j++) count++;
return count;
}
function fixedInner(n) { // an inner loop of 100, whatever n is
let count = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < 100; j++) count++;
return count;
}
function everyPair(n) { // an inner loop of n
let count = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) count++;
return count;
}
// twoLoops [2000, 4000, 8000]
// fixedInner [100000, 200000, 400000]
// everyPair [1000000, 4000000, 16000000]Loops one after another add: n + n = 2n steps, O(n). A loop inside another multiplies: n rounds of n is n², O(n²). An inner loop that runs 100 times whatever n is still multiplies by a constant, so the inner loop of 100 makes 100n steps, 100,000 at n = 1,000: O(n). It went ×2 when n doubled, like the plain loop.
When the loops run over two different inputs, keep both sizes: a loop over n values then one over m values is O(n + m), and one inside the other is O(n · m). Writing O(n) there hides the second input.
An inner loop that starts where the outer one is
long long pairsOnce(int n) { // j starts just after i
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) count++;
return count;
}
long long allTriples(int n) { // k after j, j after i
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++) count++;
return count;
}
// pairsOnce [499500, 1999000, 7998000]
// allTriples [161700, 1313400, 10586800]def pairs_once(n): # j starts just after i
count = 0
for i in range(n):
for j in range(i + 1, n):
count += 1
return count
def all_triples(n): # k after j, j after i
count = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
count += 1
return count
# pairs_once [499500, 1999000, 7998000]
# all_triples [161700, 1313400, 10586800]static long pairsOnce(int n) { // j starts just after i
long count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) count++;
return count;
}
static long allTriples(int n) { // k after j, j after i
long count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++) count++;
return count;
}
// pairsOnce [499500, 1999000, 7998000]
// allTriples [161700, 1313400, 10586800]function pairsOnce(n) { // j starts just after i
let count = 0;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++) count++;
return count;
}
function allTriples(n) { // k after j, j after i
let count = 0;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
for (let k = j + 1; k < n; k++) count++;
return count;
}
// pairsOnce [499500, 1999000, 7998000]
// allTriples [161700, 1313400, 10586800]Starting j just after i makes the inner loop run n − 1 times, then n − 2, down to 0: n(n − 1)/2 steps in all, 499,500 at n = 1,000. That's half of n², and half of n² is still O(n²): the count went ×4 when n doubled, just as n² does. Three loops that start each after the last make n(n − 1)(n − 2)/6 steps, 161,700 at n = 100: O(n³), ×8 per doubling.
Halving and doubling
long long halving(int n) { // n, n/2, n/4, ... until 1
long long count = 0;
while (n > 1) {
n /= 2;
count++;
}
return count;
}
long long doublingInside(int n) { // for each i: j = 1, 2, 4, ... up to n
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j *= 2) count++;
return count;
}
long long upToRoot(int n) { // i = 1, 2, 3, ... while i * i <= n
long long count = 0;
for (long long i = 1; i * i <= n; i++) count++;
return count;
}
// halving [9, 10, 11]
// doublingInside [10000, 22000, 48000]
// upToRoot [31, 44, 63]def halving(n): # n, n/2, n/4, ... until 1
count = 0
while n > 1:
n //= 2
count += 1
return count
def doubling_inside(n): # for each i: j = 1, 2, 4, ... up to n
count = 0
for i in range(n):
j = 1
while j < n:
j *= 2
count += 1
return count
def up_to_root(n): # i = 1, 2, 3, ... while i * i <= n
count = 0
i = 1
while i * i <= n:
i += 1
count += 1
return count
# halving [9, 10, 11]
# doubling_inside [10000, 22000, 48000]
# up_to_root [31, 44, 63]static long halving(int n) { // n, n/2, n/4, ... until 1
long count = 0;
while (n > 1) {
n /= 2;
count++;
}
return count;
}
static long doublingInside(int n) { // for each i: j = 1, 2, 4, ... up to n
long count = 0;
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j *= 2) count++;
return count;
}
static long upToRoot(int n) { // i = 1, 2, 3, ... while i * i <= n
long count = 0;
for (long i = 1; i * i <= n; i++) count++;
return count;
}
// halving [9, 10, 11]
// doublingInside [10000, 22000, 48000]
// upToRoot [31, 44, 63]function halving(n) { // n, n/2, n/4, ... until 1
let count = 0;
while (n > 1) {
n = Math.floor(n / 2);
count++;
}
return count;
}
function doublingInside(n) { // for each i: j = 1, 2, 4, ... up to n
let count = 0;
for (let i = 0; i < n; i++)
for (let j = 1; j < n; j *= 2) count++;
return count;
}
function upToRoot(n) { // i = 1, 2, 3, ... while i * i <= n
let count = 0;
for (let i = 1; i * i <= n; i++) count++;
return count;
}
// halving [9, 10, 11]
// doublingInside [10000, 22000, 48000]
// upToRoot [31, 44, 63]The halving loop divides n by 2 until it reaches 1. Starting from 1,000 that's 9 halvings, and doubling n adds just one more, because 2,000 halves to 1,000 first. The number of halvings is log₂ n, the number of times you double 1 to reach n (2¹⁰ = 1,024, so log₂ 1,024 = 10), and the loop is O(log n): a billion takes 29. A counter that doubles, 1, 2, 4, 8, reaches n in the same log₂ n steps, so n rounds of it are O(n log n): 10,000, 22,000 and 48,000.
The base doesn't matter: dividing by 3 instead takes log₃ n steps, and log₃ n is log₂ n divided by 1.58, a constant. Big O writes them all as log n.
A loop that stops once i × i passes n ran 31, 44 and 63 steps, the square roots of 1,000, 2,000 and 4,000. That's O(√n), ×1.41 per doubling. Checking whether n is prime by trying divisors up to √n works this way.
A loop that jumps by i
long long jumpsByI(int n) { // for each i: j = i, 2i, 3i, ... up to n
long long count = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j += i) count++;
return count;
}
// jumpsByI [7069, 15518, 33805]def jumps_by_i(n): # for each i: j = i, 2i, 3i, ... up to n
count = 0
for i in range(1, n + 1):
for j in range(i, n + 1, i):
count += 1
return count
# jumps_by_i [7069, 15518, 33805]static long jumpsByI(int n) { // for each i: j = i, 2i, 3i, ... up to n
long count = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j += i) count++;
return count;
}
// jumpsByI [7069, 15518, 33805]function jumpsByI(n) { // for each i: j = i, 2i, 3i, ... up to n
let count = 0;
for (let i = 1; i <= n; i++)
for (let j = i; j <= n; j += i) count++;
return count;
}
// jumpsByI [7069, 15518, 33805]The inner loop starts at i and jumps by i, so it runs n times when i = 1, n/2 times when i = 2, n/3 when i = 3, and once when i = n. The sum n/1 + n/2 + n/3 + … + n/n is n times the harmonic number, about n ln n: 7,485 for n = 1,000, where the real count with the fractions rounded down is 7,069. So two nested loops that look like n² are O(n log n): the count went ×2.20 and ×2.18. The sieve of Eratosthenes, which crosses out the multiples of each number, has this shape.
A pointer that never goes back
long long window(int n) { // n values, all 1; the window may hold 10
long long count = 0;
int left = 0, total = 0;
for (int right = 0; right < n; right++) {
total += 1; // take value number right
count++;
while (total > 10) { // left only ever moves forward
total -= 1; // drop value number left
left++;
count++;
}
}
return count;
}
// window [1990, 3990, 7990]def window(n): # n values, all 1; the window may hold 10
count = 0
left = 0
total = 0
for right in range(n):
total += 1 # take value number right
count += 1
while total > 10: # left only ever moves forward
total -= 1 # drop value number left
left += 1
count += 1
return count
# window [1990, 3990, 7990]static long window(int n) { // n values, all 1; the window may hold 10
long count = 0;
int left = 0, total = 0;
for (int right = 0; right < n; right++) {
total += 1; // take value number right
count++;
while (total > 10) { // left only ever moves forward
total -= 1; // drop value number left
left++;
count++;
}
}
return count;
}
// window [1990, 3990, 7990]function window(n) { // n values, all 1; the window may hold 10
let count = 0;
let left = 0, total = 0;
for (let right = 0; right < n; right++) {
total += 1; // take value number right
count++;
while (total > 10) { // left only ever moves forward
total -= 1; // drop value number left
left++;
count++;
}
}
return count;
}
// window [1990, 3990, 7990]A while loop inside a for loop, so O(n²)? No. left only moves forward, and it can't pass right, so across the whole run the inner loop runs at most n times. The counts were 1,990, 3,990 and 7,990: 2n − 10, O(n). This is the sliding window's loop, and the reason its while doesn't make it quadratic: count the moves of each pointer over the whole run, not the loops' shape. Amortized Analysis gives the rule behind it.
Guess the Growth. Ten loops, the ones above and a few more. For each, pick the growth you expect before running it at n, 2n and 4n; the counts come from running the loop, and the ratios show whether you were right.
Calls that hide a loop
A one-line call can be a loop. Putting a value at the front of an array moves every value after it one place; asking a list whether it holds x checks its values one at a time. Each looks like one step, and here each runs inside a loop of n:
#include <bits/stdc++.h>
using namespace std;
long long putInFront(int n) { // insert at begin() moves every item one place to the right
vector<int> items;
for (int x = 0; x < n; x++) items.insert(items.begin(), x);
return items.size();
}
long long lookUpInList(int n) { // find checks the items one at a time
vector<int> items(n);
iota(items.begin(), items.end(), 0);
long long found = 0;
for (int x = 0; x < n; x++)
if (find(items.begin(), items.end(), x) != items.end()) found++;
return found;
}
double seconds(long long (*f)(int), int n) { // the fastest of five runs
double best = 1e9;
for (int run = 0; run < 5; run++) {
auto start = chrono::steady_clock::now();
if (f(n) < 0) puts("?");
best = min(best, chrono::duration<double>(chrono::steady_clock::now() - start).count());
}
return best;
}
int main() {
pair<const char*, long long (*)(int)> fs[] = {{"putInFront", putInFront}, {"lookUpInList", lookUpInList}};
int sizes[] = {20000, 20000};
for (int k = 0; k < 2; k++) {
auto [name, f] = fs[k];
int n = sizes[k];
for (int w = 0; w < 3; w++) f(4 * n); // warm up on the biggest input first
double t1 = seconds(f, n), t2 = seconds(f, 2 * n), t4 = seconds(f, 4 * n);
printf("%s: %.4fs %.4fs %.4fs (x%.1f, x%.1f)\n", name, t1, t2, t4, t2 / t1, t4 / t2);
}
}
// putInFront: 0.0136s 0.0565s 0.2271s (x4.2, x4.0)
// lookUpInList: 0.0492s 0.1963s 0.7826s (x4.0, x4.0)import time
def put_in_front(n): # insert(0, x) moves every item one place to the right
items = []
for x in range(n):
items.insert(0, x)
return len(items)
def look_up_in_list(n): # x in items checks the items one at a time
items = list(range(n))
found = 0
for x in range(n):
if x in items:
found += 1
return found
def seconds(f, n): # the fastest of five runs
best = float("inf")
for _ in range(5):
start = time.perf_counter()
f(n)
best = min(best, time.perf_counter() - start)
return best
for f, n in ((put_in_front, 12500), (look_up_in_list, 2500)):
for _ in range(3): # warm up on the biggest input first
f(4 * n)
t1, t2, t4 = seconds(f, n), seconds(f, 2 * n), seconds(f, 4 * n)
print(f"{f.__name__}: {t1:.4f}s {t2:.4f}s {t4:.4f}s (x{t2 / t1:.1f}, x{t4 / t2:.1f})")
# put_in_front: 0.0521s 0.2071s 0.8238s (x4.0, x4.0)
# look_up_in_list: 0.0359s 0.1432s 0.5795s (x4.0, x4.0)import java.util.*;
import java.util.function.IntToLongFunction;
public class Main {
static long putInFront(int n) { // add(0, x) moves every item one place to the right
List<Integer> items = new ArrayList<>();
for (int x = 0; x < n; x++) items.add(0, x);
return items.size();
}
static long lookUpInList(int n) { // contains checks the items one at a time
List<Integer> items = new ArrayList<>();
for (int v = 0; v < n; v++) items.add(v);
long found = 0;
for (int x = 0; x < n; x++)
if (items.contains(x)) found++;
return found;
}
static double seconds(IntToLongFunction f, int n) { // the fastest of five runs
double best = Double.MAX_VALUE;
for (int run = 0; run < 5; run++) {
long start = System.nanoTime();
if (f.applyAsLong(n) < 0) System.out.println("?");
best = Math.min(best, (System.nanoTime() - start) / 1e9);
}
return best;
}
public static void main(String[] args) {
String[] names = {"putInFront", "lookUpInList"};
IntToLongFunction[] fs = {Main::putInFront, Main::lookUpInList};
int[] sizes = {10000, 10000};
for (int k = 0; k < 2; k++) {
int n = sizes[k];
for (int w = 0; w < 3; w++) fs[k].applyAsLong(4 * n); // warm up: Java compiles a method as it runs
double t1 = seconds(fs[k], n), t2 = seconds(fs[k], 2 * n), t4 = seconds(fs[k], 4 * n);
System.out.printf("%s: %.4fs %.4fs %.4fs (x%.1f, x%.1f)%n", names[k], t1, t2, t4, t2 / t1, t4 / t2);
}
}
}
// putInFront: 0.0040s 0.0184s 0.0763s (x4.6, x4.1)
// lookUpInList: 0.0386s 0.1543s 0.6170s (x4.0, x4.0)function putInFront(n) { // unshift moves every item one place to the right
const items = [];
for (let x = 0; x < n; x++) items.unshift(x);
return items.length;
}
function lookUpInList(n) { // includes checks the items one at a time
const items = Array.from({ length: n }, (_, v) => v);
let found = 0;
for (let x = 0; x < n; x++)
if (items.includes(x)) found++;
return found;
}
function seconds(f, n) { // the fastest of five runs
let best = Infinity;
for (let run = 0; run < 5; run++) {
const start = process.hrtime.bigint();
if (f(n) < 0) console.log("?");
best = Math.min(best, Number(process.hrtime.bigint() - start) / 1e9);
}
return best;
}
for (const [f, n] of [[putInFront, 10000], [lookUpInList, 10000]]) {
for (let w = 0; w < 3; w++) f(4 * n); // warm up on the biggest input first
const t1 = seconds(f, n), t2 = seconds(f, 2 * n), t4 = seconds(f, 4 * n);
console.log(`${f.name}: ${t1.toFixed(4)}s ${t2.toFixed(4)}s ${t4.toFixed(4)}s ` +
`(x${(t2 / t1).toFixed(1)}, x${(t4 / t2).toFixed(1)})`);
}
// putInFront: 0.0073s 0.0293s 0.1156s (x4.0, x3.9)
// lookUpInList: 0.0984s 0.3922s 1.5649s (x4.0, x4.0)| Language | Put at the front, n times | Look up in a list, n times |
|---|---|---|
C++ (insert, find) | ×4.2, then ×4.0 | ×4.0, then ×4.0 |
Python (insert(0, x), in) | ×4.0, then ×4.0 | ×4.0, then ×4.0 |
Java (add(0, x), contains) | ×4.6, then ×4.1 | ×4.0, then ×4.0 |
JavaScript (unshift, includes) | ×4.0, then ×3.9 | ×4.0, then ×4.0 |
Every one went about ×4 per doubling: an O(n) call inside a loop of n is O(n²). The fix is a structure built for the job: a deque for the front (collections.deque, ArrayDeque, std::deque) and a set for look-ups. Taking from the front, with pop(0) or shift(), costs the same way; Introduction to Queues timed it.
Adding to a string one character at a time. A Java String never changes, so s = s + "a", and s += "a" too, makes a new string and copies the old one into it, every time:
import java.util.function.IntToLongFunction;
public class Main {
static long copyEveryTime(int n) { // s + "a" builds a new string: a copy of s, then "a"
String s = "";
for (int i = 0; i < n; i++) s = s + "a";
return s.length();
}
static long addInPlace(int n) { // a StringBuilder grows where it is, like an ArrayList
StringBuilder s = new StringBuilder();
for (int i = 0; i < n; i++) s.append('a');
return s.length();
}
static double seconds(IntToLongFunction f, int n) { // the fastest of five runs
double best = Double.MAX_VALUE;
for (int run = 0; run < 5; run++) {
long start = System.nanoTime();
if (f.applyAsLong(n) < 0) System.out.println("?");
best = Math.min(best, (System.nanoTime() - start) / 1e9);
}
return best;
}
public static void main(String[] args) {
String[] names = {"copyEveryTime", "addInPlace"};
IntToLongFunction[] fs = {Main::copyEveryTime, Main::addInPlace};
int[] sizes = {25000, 2500000};
for (int k = 0; k < 2; k++) {
int n = sizes[k];
for (int w = 0; w < 3; w++) fs[k].applyAsLong(4 * n); // warm up: Java compiles a method as it runs
double t1 = seconds(fs[k], n), t2 = seconds(fs[k], 2 * n), t4 = seconds(fs[k], 4 * n);
System.out.printf("%s: %.4fs %.4fs %.4fs (x%.1f, x%.1f)%n", names[k], t1, t2, t4, t2 / t1, t4 / t2);
}
}
}
// copyEveryTime: 0.0345s 0.1599s 0.6328s (x4.6, x4.0)
// addInPlace: 0.0056s 0.0082s 0.0176s (x1.5, x2.2)The copy went ×4.6 and ×4.0 per doubling: O(n²) for a string of n characters. The StringBuilder grows in place, like an ArrayList; it handled 100 times as many characters and went ×1.5 and ×2.1. C++ has both kinds too: s = s + 'a' builds a new string from a copy of s, and s += 'a' grows s where it is:
string copyEveryTime(int n) { // s + 'a' builds a new string: a copy of s, then 'a'
string s;
for (int i = 0; i < n; i++) s = s + 'a';
return s;
}
string addInPlace(int n) { // += 'a' grows s where it is, like a vector
string s;
for (int i = 0; i < n; i++) s += 'a';
return s;
}Python and JavaScript avoided the copy in this loop on our judge, but Python doesn't promise to. Joining a list of pieces at the end ("".join(parts), parts.join("")) is safe in both.
Memory counts too
Space complexity is the same idea for memory: how the extra memory a program needs grows with n. Count what you create, the arrays, sets and maps, and the call stack of a recursion; the input itself usually isn't counted. The three repeat checks:
| Way | Time | Extra memory |
|---|---|---|
| Every pair | O(n²) | O(1): two indexes |
| Sort a copy, then neighbours | O(n log n) | O(n): the copy |
| A set | O(n) | O(n): up to n values in the set |
The fastest one pays for its speed with memory, which is the usual trade, and an interviewer expects both numbers. A recursion n calls deep keeps n frames on the call stack, O(n) space even when it creates nothing; Introduction to Recursion measured how deep each language lets you go.
What Big O leaves out
Small inputs. Big O describes what happens as n grows; on small inputs the constants win. On our judge, insertion sort, which is O(n²), beat merge sort, O(n log n), on every size up to 256 values in C++ and lost from 384 on; in Python it won up to 40 and lost from 48. Library sorts use this: GCC's std::sort finishes ranges of 16 values or fewer with insertion sort, and Python's sort sorts any list shorter than 64 with insertion sort.
The machine. Even on one machine, Big O can't promise seconds. We built the C++ pair check eight times, each with a different number of do-nothing instructions, 0 to 28 bytes of them, in front of its loop: the same instructions on the same values, only moved along in memory. The slowest build:
__attribute__((noinline, aligned(64))) // the function starts on a 64-byte boundary
bool hasDuplicatePairs(const vector<int>& nums) {
asm volatile(".rept 16\n nop\n .endr"); // 16 do-nothing bytes, then the loop
for (size_t i = 0; i < nums.size(); i++)
for (size_t j = i + 1; j < nums.size(); j++)
if (nums[i] == nums[j]) return true;
return false;
}On 100,000 values the builds took between 1.63 s and 3.63 s: the processor runs a short loop faster from some addresses than from others. Every build still went ×4.0 to ×4.3 from 50,000 values to 100,000. That is the constant Big O drops: it moves with things the code doesn't show, while the growth stays put.
Big numbers. Big O counts an addition or a multiplication as one step, which is true while the numbers fit in 64 bits. Python's integers and JavaScript's BigInt grow without limit, and multiplying a long one takes time in proportion to its length:
import time
def factorial(n):
result = 1
for k in range(2, n + 1): # n - 1 multiplications
result *= k
return result
previous = None
for n in (5000, 10000, 20000, 40000):
start = time.perf_counter()
bits = factorial(n).bit_length()
took = time.perf_counter() - start
growth = f", x{took / previous:.1f}" if previous else ""
print(f"{n}! has {bits} bits: {took:.4f}s{growth}")
previous = took
# 5000! has 54233 bits: 0.0051s
# 10000! has 118459 bits: 0.0205s, x4.0
# 20000! has 256909 bits: 0.0866s, x4.2
# 40000! has 553810 bits: 0.3777s, x4.4function factorial(n) {
let result = 1n;
for (let k = 2n; k <= BigInt(n); k++) // n - 1 multiplications
result *= k;
return result;
}
let previous = null;
for (const n of [5000, 10000, 20000, 40000]) {
const start = process.hrtime.bigint();
const bits = factorial(n).toString(2).length;
const took = Number(process.hrtime.bigint() - start) / 1e9;
const growth = previous ? `, x${(took / previous).toFixed(1)}` : "";
console.log(`${n}! has ${bits} bits: ${took.toFixed(4)}s${growth}`);
previous = took;
}
// 5000! has 54233 bits: 0.0088s
// 10000! has 118459 bits: 0.0272s, x3.1
// 20000! has 256909 bits: 0.1024s, x3.8
// 40000! has 553810 bits: 0.4059s, x4.0The loop runs n − 1 times, but each multiplication is longer than the last, so the time went ×4.0 to ×4.4 per doubling in Python and ×3.1 to ×4.0 in JavaScript: closer to n² than to n. In C++, and in Java with a long, the number would overflow instead, past 20 factorial.
An upper bound, not an exact answer. Strictly, f(n) = O(g(n)) means that past some n₀, f(n) ≤ c · g(n) for a fixed c. So on paper an O(n) algorithm is also O(n²). Textbooks write the tight answer as Θ (theta), and a lower bound as Ω (omega); interviewers say Big O and mean the tight one. Give the tightest growth you can show.
Mistakes that cost an interview
"Two loops, so O(n²)." Count the steps, not the loops: the window loop has a while inside a for and ran 7,990 steps at n = 4,000, and the loop that jumps by i is O(n log n).
"One loop, so O(n)." A call inside the loop counts: x in items on a list, contains on an ArrayList or includes on an array made a loop of 10,000 look-ups take 98 ms in JavaScript and 1.56 s at 40,000.
"I sort it, so the rest is O(n)." The sort costs O(n log n) itself, so the whole is O(n log n). And a sort inside a loop of n is O(n² log n).
One size for two inputs. Two loops over two arrays are O(n + m), and nested they're O(n · m). Calling either O(n) is wrong when m can be much bigger than n.
O(2n), O(n/2), O(log₂ n). Not wrong, but say O(n), O(n) and O(log n): constants and log bases drop out.
Forgetting the space. "What's the space?" is the usual follow-up. Count the set, the copy and the call stack.
Check yourself
Quiz
1 / 6Multiple choice
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
count++;Multiple choice
long long count = 0;
while (n > 0) {
n /= 3;
count++;
}Multiple choice
Multiple choice
items is a list of n values and queries holds n values. What is the time complexity?long long count = 0;
for (int x : queries) // n queries
if (find(items.begin(), items.end(), x) != items.end()) // items: n values
count++;Multiple choice
long long count = 0;
for (int i = 0; i < n; i++) // n values in the first list
count++;
for (int j = 0; j < m; j++) // m values in the second
count++;Multiple choice
nums?vector<int> result;
for (int i = (int)nums.size() - 1; i >= 0; i--)
result.push_back(nums[i]);Practice
Complexity Analysis Primer, in this section, gives more code to classify. Then the next three lessons: Best, Worst and Average Case (one algorithm, different inputs), Amortized Analysis (a cost that is sometimes large but rare) and Recurrence Relations and the Master Theorem (the cost of a recursion). Complexity Quiz: Easy, Medium and Hard, at the end of this section, mix loops, recursions and library calls, every answer checked on our judge.
Every lesson in this course states its costs and the reason for them; from here on, check each one as you read it.