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 → target complexity (≈10⁸ ops/sec)
ConstraintAim for
n ≤ 10O(n!) — try every permutation
n ≤ 20O(2ⁿ · n) — subsets / bitmask
n ≤ 500O(n³)
n ≤ 5,000O(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

Same task, two complexities
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

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.

  1. A loop runs i = 1, 2, 4, 8, ... until i reaches n. How many times does it run?

  2. Two nested loops each run n times, followed by one separate loop of n steps. What is the total time?

  3. n can be up to 100,000 and the time limit is one second. Which complexity is the slowest that still passes comfortably?

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.

Stuck on Big-O?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor