Describing Time Complexity
Big-O in plain English: O(1), O(log N), O(N), O(N log N), O(N²) — what they mean for real code
Big-O plain English
- O(1) — constant; same speed regardless of input size (hash map lookup, array access)
- O(log N) — logarithmic; doubles input → adds one step (binary search)
- O(N) — linear; doubles input → doubles time (single loop)
- O(N log N) — linearithmic; efficient sorting; slightly worse than linear
- O(N²) — quadratic; nested loops; doubles input → 4× time; avoid for large N
Question 0 of 5
A colleague says: "This function runs in O(1) time." What does that mean in plain English?
Constant time — execution time does not grow with input size. Big-O plain English vocabulary:
- O(1) — constant time; array index access, hash map lookup, stack push/pop
- O(log N) — logarithmic; binary search; doubles the input → adds just one step
- O(N) — linear; single loop through N elements; doubles input → doubles time
- O(N log N) — linearithmic; efficient sorting (merge sort, quicksort); doubles input → slightly more than doubles time
- O(N²) — quadratic; nested loops; doubles input → 4× the time
- O(2^N) — exponential; brute-force combinatorics; adding 1 to input → doubles time
Code review comment: "This nested loop gives O(N²) complexity. For the current dataset size of 10,000 items, that's 100 million operations." Why is this a concern?
O(N²) means 10× more data → 100× slower — unacceptable for growing datasets. How to communicate complexity concerns in code review:
- State the complexity: "This is O(N²) due to the nested loop."
- Quantify the current impact: "At N=10,000, that's 10^8 operations."
- Project to production scale: "Our user base is at 50,000 now — that's 2.5 billion operations."
- Suggest the fix: "Can we use a hash set here to bring this down to O(N)?"
Which of these accurately describes O(N log N) in plain language?
Both descriptions are valid — O(N log N) can arise from different structures. Explaining O(N log N) in different contexts:
- Efficient sorting: merge sort divides the array log N times, each division processing N elements → N log N total
- N binary searches: if you binary-search a sorted array for each of N items → N × O(log N) = O(N log N)
- Building a sorted structure: inserting N items into a balanced BST → N × O(log N) per insert
A PR description says: "Reduced lookup from O(N) to O(1) by replacing the array search with a Map." What changed in the code?
A hash map stores data by key for O(1) lookup instead of scanning all elements. Data structure + complexity vocabulary:
- Array/list search — O(N); must check each element; no index
- Hash map/dict/Map — O(1) average lookup, insert, delete; stores key→value pairs; uses hashing
- Set — O(1) average membership check; like a hash map with only keys
- Sorted array + binary search — O(log N) lookup; O(N log N) to build
- BST (balanced) — O(log N) lookup, insert, delete
How would you explain this code's time complexity to a junior developer?for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
compare(arr[i], arr[j]);
}
}
O(N²) — even though the inner loop shrinks, it's still proportional to N². Explaining nested loops to a junior developer:
- Outer loop: N iterations. Inner loop: N-1, N-2, ..., 1 iterations → sum = N(N-1)/2
- N(N-1)/2 simplifies to O(N²) — we drop constants and lower-order terms in Big-O
- Conceptual explanation: "For every element, we compare it to every element that comes after it. If we have 100 items, that's roughly 5,000 comparisons. 1,000 items → 500,000 comparisons."