Time & Space Complexity (Big-O) — Explained Simply

Before you learn a single data structure, learn how to measure code. In every interview, after you write a solution, the interviewer asks the same question: "What is the time and space complexity?" This lesson teaches you to answer it with confidence.

Why not just measure the time in seconds?

Run the same program on a gaming laptop and on a 5-year-old phone and you get two different numbers. Seconds depend on the machine. We need a measure that depends only on the algorithm.

So we ask a better question: as the input grows, how fast does the work grow? If the input becomes 10× bigger, does the work stay the same, grow 10×, or grow 100×? That growth rate is what Big-O describes.

Big-O = how the number of steps grows with input size n, ignoring constants and small terms.

The complexities you will see 95% of the time

Big-O	Name	n = 1,000 → steps (roughly)	Example
O(1)	Constant	1	Access arr[5], push to a stack
O(log n)	Logarithmic	10	Binary search
O(n)	Linear	1,000	One loop over the array
O(n log n)	Linearithmic	10,000	Merge sort, sort()
O(n²)	Quadratic	1,000,000	Two nested loops
O(2ⁿ)	Exponential	astronomical	All subsets

Rule of thumb for coding tests: a computer does about 10⁸ simple operations per second. If n is up to 10⁵, an O(n²) solution does 10¹⁰ steps — too slow. You need O(n log n) or O(n).

If n is up to…	You can afford
10–20	O(2ⁿ) — try all subsets
500	O(n³)
5,000	O(n²)
10⁵ – 10⁶	O(n log n) or O(n)
10⁹+	O(log n) or O(1)

This table alone often tells you which algorithm the interviewer expects.

How to calculate Big-O: 4 rules

1. Sequential steps add, nested steps multiply.

for i in range(n):        # n steps
    print(i)
for j in range(n):        # n steps
    print(j)
# total: n + n = 2n  →  O(n)

for i in range(n):        # n times …
    for j in range(n):    # … n steps each
        print(i, j)
# total: n × n  →  O(n²)

2. Drop constants. 2n, 3n + 5, n/2 are all O(n). Big-O is about growth, not exact counts.

3. Keep only the biggest term. n² + n + 100 → O(n²). For large n, the n² part dominates everything else.

4. Different inputs get different letters. Looping over array a (size n) and then array b (size m) is O(n + m), not O(n). Nested over both is O(n × m).

Where does O(log n) come from?

Whenever you halve the problem at each step, you get log n. Start with 1,000 items: 1000 → 500 → 250 → … → 1. That is only about 10 halvings (because 2¹⁰ ≈ 1,000). For a million items it is about 20.

def count_halvings(n):
    steps = 0
    while n > 1:
        n //= 2      # problem size halves
        steps += 1
    return steps     # ≈ log2(n)  →  O(log n)

This is why binary search on a million sorted numbers needs only ~20 comparisons.

Space complexity

Space complexity measures extra memory your algorithm uses as n grows (we usually don't count the input itself).

// O(1) extra space — a few variables, whatever n is
int sum(int[] arr) {
    int total = 0;
    for (int x : arr) total += x;
    return total;
}

// O(n) extra space — a new array of size n
int[] doubled(int[] arr) {
    int[] out = new int[arr.length];
    for (int i = 0; i < arr.length; i++) out[i] = arr[i] * 2;
    return out;
}

Recursion uses space too. Every recursive call waits on the call stack. A recursion that goes n levels deep uses O(n) space, even if it creates no arrays.

Worked example: two ways to find a duplicate

Problem: does an array contain any value twice?

Brute force — compare every pair:

def has_duplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False
# Time O(n²), space O(1)

Better — remember what you've seen in a set:

def has_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:        # set lookup is O(1) on average
            return True
        seen.add(x)
    return False
# Time O(n), space O(n)

boolean hasDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) {
        if (!seen.add(x)) return true; // add() returns false if already present
    }
    return false;
}

We traded memory for speed — O(n) extra space to go from O(n²) to O(n). This time–space trade-off is the single most common idea in DSA interviews.

Best, average and worst case

• Worst case — the slowest possible input (what Big-O usually means in interviews).
• Average case — typical input. Hash map lookups are O(1) on average, O(n) in the rare worst case.
• Best case — rarely useful ("linear search is O(1) if the item is first" doesn't help anyone).

When in doubt, answer with the worst case and mention the average if it's different.

Common mistakes

1. Hidden loops. x in my_list (Python) or list.contains(x) (Java) is O(n), not O(1). Putting it inside a loop makes your "O(n)" solution secretly O(n²). Use a set or map.
2. String building in a loop. In Java, s = s + c inside a loop copies the string each time → O(n²). Use StringBuilder.
3. Forgetting sort costs. If you sort first, your solution is at least O(n log n).
4. Ignoring recursion depth when asked about space.

How to answer in an interview

Say it in one breath: "Time is O(n) because we visit each element once and each set operation is O(1) on average. Space is O(n) for the set in the worst case when all elements are distinct." — the complexity plus the reason. That reason is what interviewers are really checking.

Key takeaways

• Big-O describes growth, not seconds. Drop constants and smaller terms.
• Sequential → add; nested → multiply; halving → log n.
• Use the constraints table to guess the expected complexity before you code.
• Most optimisations trade space for time — usually with a hash set or hash map.

Next: we put this to work on the most common interview topic of all — arrays and hashing.