Big O describes how work grows as input grows. Learn the five common shapes, how to read them from code, and a simple trick that turns O(n squared) into O(n).

Big O sounds like advanced maths, but the idea is something you already know. If a task takes twice as long when you double the work, that is one kind of growth. If it takes four times as long, that is another. Big O is simply a short way of naming that growth.

In interviews, you will be asked “what is the time complexity?” after almost every solution. Here is how to answer with confidence.

The big idea: how work grows

Big O ignores exact seconds, because those depend on your computer. It asks a better question: as the input gets bigger, how fast does the work grow? We call the input size n.

Say a list has 1,000 items. Here is roughly how many steps each common shape needs:

The gap between shapes explodes as n grows.

The five shapes you will meet

NamePlain meaningEveryday example
O(1) constantSame work no matter the sizeReading items[5], or looking up a key in a hash map
O(log n) logarithmicCut the problem in half each stepBinary search in a sorted list
O(n) linearLook at each item onceLooping through a list to find the largest
O(n log n)Split in half, then handle every itemGood sorting algorithms like merge sort
O(n²) quadraticFor each item, look at every itemA loop inside a loop over the same list

How to read it from code

You can work out most answers with three habits:

  1. Count the loops. One loop over the data is O(n). A loop inside a loop is usually O(n²).
  2. Drop constants and small terms. O(2n + 5) is just O(n). Big O is about the shape, not the exact count.
  3. Halving means log. If each step throws away half the remaining data, think O(log n).
shapes.py
def first(items):            # O(1)
    return items[0]

def biggest(items):          # O(n), one pass
    best = items[0]
    for x in items:
        if x > best:
            best = x
    return best

def has_pair(items):         # O(n^2), loop inside loop
    for a in items:
        for b in items:
            if a != b and a + b == 10:
                return True
    return False

The classic trade: memory for speed

Many interview problems have a slow solution and a fast one that uses extra memory. The famous example is “find two numbers that add up to a target”. The nested loop above is O(n²). Using a set to remember what you have seen makes it O(n):

two_sum.py
def has_pair(items, target):   # O(n) time, O(n) extra memory
    seen = set()
    for x in items:
        if target - x in seen:   # a set lookup is O(1)
            return True
        seen.add(x)
    return False
You spend memory to buy speed. Say the trade-off out loud.

Space complexity and best versus worst case

Interviewers may also ask about space complexity, which uses the same notation but counts extra memory instead of steps. The set above uses O(n) space.

Also remember that one algorithm can behave differently depending on the input. Searching a list for a value takes one step if it is first (best case) and n steps if it is last or missing (worst case). Unless told otherwise, quote the worst case.

How to sound confident in the interview

  • State the answer first: “This is O(n log n) because we sort, then do one pass.”
  • Name the part that dominates. The slowest step decides the final answer.
  • After a working solution, ask yourself: “Can I trade memory for speed?”
  • If you are unsure, reason out loud. Showing the thinking earns credit even if the final label is slightly off.