Big O Notation Explained for Coding Interviews: Time and Space Complexity Made Simple

After you write a solution, the next thing an interviewer asks is almost always: what is the time and space complexity? Big O is just a way of describing how the work grows as the input grows. You do not need heavy math for it. You need a few common classes, a habit of counting loops, and awareness of the hidden costs in your language. The examples below use Python.

What Big O really measures

Big O describes how the number of steps (time complexity) or the amount of memory (space complexity) grows as the input size, usually called n, grows. It deliberately ignores small details such as the speed of your computer or the exact number of instructions. Two programs that both double their running time when the input doubles belong to the same growth class, even if one is a little faster in practice. Big O usually describes the worst case, unless you say otherwise.

The common complexities

To feel the difference, take n = 1,000. A logarithmic algorithm needs about 10 steps, a linear one 1,000, a linearithmic one about 10,000 and a quadratic one 1,000,000. An exponential algorithm would need a number of steps with more than 300 digits, which is why exponential solutions only work for tiny inputs.

How to calculate time complexity

1. Count the loops. One loop over n items is O(n). A loop inside a loop, both over n, is O(n²).
2. Add sequential steps. An O(n) loop followed by another O(n) loop is O(2n), which simplifies to O(n).
3. Multiply nested steps. A loop of n iterations that calls an O(log n) function is O(n log n).
4. Drop constants and smaller terms. O(3n + 10) becomes O(n), and O(n² + n) becomes O(n²).
5. Use different letters for different inputs. Looping over two separate arrays of sizes a and b is O(a + b), not O(n).

For example, this function is O(n) because it makes a single pass:

def contains(nums, x):
    for n in nums:
        if n == x:
            return True
    return False

And this one is O(n²) because for each element it scans the rest of the array:

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

Using a set turns it into O(n) time with O(n) space: loop once and check whether each number was already seen.

Space complexity

Space complexity counts the extra memory your algorithm uses beyond the input. A few variables are O(1). A new list or dictionary that can grow to the size of the input is O(n). Recursion also uses memory, because each active call sits on the call stack, so a recursive function that goes n levels deep uses O(n) stack space even if it creates no lists.

Amortized analysis in one paragraph

Appending to a Python list is usually O(1), but occasionally the list has to grow and copy all its elements, which costs O(n). Because that expensive step happens rarely, the average cost per append over many operations is still constant. This is called amortized O(1). It is a good phrase to know when an interviewer asks about dynamic arrays.

Complexities of common Python operations

Hidden costs that surprise candidates

• Slicing and copying. Passing nums[1:] into a recursive call copies the list every time, turning an O(n) idea into O(n²).
• Membership in a list. Checking x in nums inside a loop creates O(n²) code.
• Removing from the front. Using a list as a queue with pop(0) is slow. Use collections.deque.
• String building. Adding characters to a string in a loop can be quadratic. Collect pieces in a list and call ''.join() once.

Using constraints to guess the expected complexity

Problem statements usually give limits on n. These limits hint at what complexity is intended, assuming roughly 10⁸ simple operations per second.

How to talk about complexity in an interview

State the time and space complexity after you finish the code, and justify each in one sentence, for example: This is O(n) time because we scan the array once, and O(n) space for the hash map. Mention the brute force complexity first, then explain what makes your approach better. If you are unsure, reason through the loops aloud. Showing the reasoning matters as much as the final answer.

Three snippets to analyse before you read the answers

Reading about Big O is easy; applying it to unfamiliar code is the skill. Decide the time complexity of each function before you look below it.

def pair_sums(nums):
    total = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            total += nums[j]
    return total

def steps(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

def has_duplicate(nums):
    seen = []
    for x in nums:
        if x in seen:
            return True
        seen.append(x)
    return False

First function: O(n²). The inner loop runs n times, then n – 1, then n – 2, down to 1. That adds up to n(n + 1) / 2 iterations. Starting j at i instead of 0 halves the work but does not change the growth rate, which is why the constant disappears.

Second function: O(log n). The input is cut in half on every pass, so the number of passes is the number of times n can be halved before reaching 1.

Third function: O(n²) in the worst case. It looks like a single loop, but x in seen scans a list, which costs O(n) each time. Replace the list with a set and the same logic runs in O(n) on average. This is the most common way a correct-looking solution turns out to be slow, and it is the reason the cost table earlier in this guide is worth memorising.

Make it a routine: after each practice problem, write the time and space complexity with a one-line reason, then compare with the editorial. The Two Sum walkthrough is a good first test because it has a clean jump from O(n²) to O(n), and building a hash table shows why dictionary lookups are treated as constant time.