Algorithms from zero
Thinking & complexity: code reading
Crux Read real code snippets, count the steps, derive the Big-O for time and space, predict behaviour, and spot the complexity or correctness bug.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skyAnalysis only sticks when you do it on real code. Read each snippet, count the loops and the memory, and decide its complexity — the exact move you make when reviewing a pull request or sizing up a solution.
Goal
Practise the loop you run on any unfamiliar function: find the dominant work, multiply nested loops, separate time from space, and notice when the trouble is not speed at all but a correctness bug.
Snippet 1 — what does the nesting cost?
function countCloserPairs(points, threshold) {
let count = 0;
for (let i = 0; i < points.length; i++) {
for (let j = i + 1; j < points.length; j++) {
if (Math.abs(points[i] - points[j]) < threshold) {
count++;
}
}
}
return count;
} Quiz
Completed
What are the time and space complexities of countCloserPairs on n points?
Heads-up There are two nested loops, so it is O(n²) time, not O(n). And space counts memory structures, not the value of count — three scalar variables is O(1).
Heads-up It inspects ~n² pairs but never stores them — it only increments a counter. Space is O(1); the n² is the time, not the memory.
Heads-up Starting j at i+1 halves the constant (n(n−1)/2 instead of n²) but the dominant term is still n². It is O(n²), not O(n log n).
Snippet 2 — predict the comparison count
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// arr = [0, 1, 2, ..., 999] (1000 sorted elements) Quiz
Completed
For arr = [0..999], which statement about linearSearch is correct?
Heads-up Being sorted does not make a linear scan logarithmic — this code ignores the order and checks every element. You would need binary search to exploit the sort and get O(log n).
Heads-up Best-case is 1 (target at index 0); worst-case is n (target last or absent). The average is ~n/2, but Big-O reports the worst case, O(n).
Heads-up Early return helps only when the target is near the front. For a missing value or one at the end, it scans all n elements — worst-case O(n).
Snippet 3 — same output, different cost
// Version A
function sumToNLoop(n) {
let sum = 0;
for (let i = 1; i <= n; i++) sum += i;
return sum;
}
// Version B
function sumToNFormula(n) {
return n * (n + 1) / 2;
} Quiz
Completed
Both functions return the same value. How do their complexities compare?
Heads-up Version B computes no sum — it applies the closed-form n(n+1)/2 in a constant number of operations. The result matches, but the cost is O(1), not O(n).
Heads-up Depending on the VALUE of n is not the same as scaling with n. B does the same handful of arithmetic ops whether n is 5 or 5 billion — that is O(1).
Heads-up A loop bounded by n runs n times, so it is O(n), not O(1). Only a loop with a fixed bound independent of n is constant time.
Snippet 4 — the bug a test might miss
function average(numbers) {
let sum = 0;
for (let i = 0; i < numbers.length; i++) {
sum += numbers[i];
}
return sum / numbers.length;
} Quiz
Completed
The complexity is fine — O(n) time, O(1) space. But what edge case breaks correctness, and why does that matter here?
Heads-up O(n) is feasible for huge inputs — that is not a correctness bug. The defect is the empty-array case producing NaN, independent of size.
Heads-up A negative average is a perfectly valid result for negative inputs — no bug. The genuine edge case is the empty array dividing by zero.
Heads-up Passing tests is not a proof of correctness. The author simply never tested the empty array, where length 0 makes the division NaN.
Recap
Reading complexity off code is a fixed routine: find the dominant work and keep only that term; multiply nested loops and add sequential phases; count memory structures, not loop iterations, for space; and remember a closed form can replace an O(n) loop with O(1). Then check the other axis — an algorithm with perfect Big-O can still be wrong on the edge case (empty input, division by zero) that your tests never touched.