Overview
Every DSA problem is really two problems: get a correct answer, and get it fast enough. Big-O notation is the language for the second part. It describes how the running time or memory of an algorithm grows as the input grows, ignoring machine speed and constant factors. An O(n) algorithm that takes one second on 10 million items will take about two seconds on 20 million; an O(n²) one will take four times as long.
In practice, complexity analysis is how you read a problem's constraints. Online judges run roughly 10⁸ simple operations per second, so when a problem says n ≤ 10⁵, an O(n²) solution (10¹⁰ operations) will time out while O(n log n) passes comfortably. Learning to do this estimate in your head before coding saves more time than any other single habit.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Constraint | Aim for |
|---|---|
| n ≤ 10 | O(n!) — try every permutation |
| n ≤ 20 | O(2ⁿ · n) — subsets / bitmask |
| n ≤ 500 | O(n³) |
| n ≤ 5,000 | O(n²) |
| n ≤ 10⁶ | O(n log n) or O(n) |
| n ≤ 10¹⁸ | O(log n) or O(1) — maths or binary search |
Patterns to recognise
Count the loops
Use it for: Nested loops multiply, sequential loops add.
A loop inside a loop over the same array is O(n²); two separate passes are O(2n) = O(n).
Halving means log n
Use it for: Any loop that cuts the problem in half each step.
Binary search, repeated division by 2 and balanced-tree height all give O(log n).
Recurrences
Use it for: Recursive divide-and-conquer code.
T(n) = 2T(n/2) + O(n) solves to O(n log n) (merge sort). T(n) = T(n/2) + O(1) is O(log n).
Code template
def has_duplicate_slow(nums): # O(n^2) time, O(1) space
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_fast(nums): # O(n) time, O(n) space
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return False
bool hasDuplicateSlow(const vector<int>& nums) { // O(n^2) time, O(1) space
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 hasDuplicateFast(const vector<int>& nums) { // O(n) time, O(n) space
unordered_set<int> seen;
for (int x : nums) {
if (seen.count(x)) return true;
seen.insert(x);
}
return false;
}
Common mistakes
- Hidden linear costs:
x in list,list.pop(0), slicing and string concatenation in a loop are all O(n) per call. - Forgetting the recursion stack when stating space complexity.
- Hash map operations are O(1) on average but O(n) in the worst case — mention it if asked.
- Trading time for space is the most common optimisation: the fast version above uses O(n) memory to save a factor of n in time.
Quick check
Three questions on Big-O. Get all three right to earn +15 XP.
-
A loop runs i = 1, 2, 4, 8, ... until i reaches n. How many times does it run?
i doubles each step, so it reaches n after about log2(n) steps.
-
Two nested loops each run n times, followed by one separate loop of n steps. What is the total time?
n^2 + n steps. Big-O keeps the fastest-growing term, so it is O(n^2).
-
n can be up to 100,000 and the time limit is one second. Which complexity is the slowest that still passes comfortably?
n log n is under 2 million steps. n^2 would be 10 billion, far too slow.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Contains DuplicateLeetCode Easy +20
- Missing NumberLeetCode Easy +20
- Squares of a Sorted ArrayLeetCode Easy +20
- Majority ElementLeetCode Easy +20
Stuck on Big-O?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor