Time and Space Complexity, Explained Simply

Why we measure algorithms at all

You have written programs that work. Now comes the next question: is this program good enough when the data gets big?

A program that sorts 10 names instantly might take an hour on 10 lakh names. A program that finds a student's marks in a list might be fine in a class of 60 and hopeless in a database of 60 million. The difference is not the language, the laptop, or how neat the code looks. It is the algorithm — the method you chose.

So we need a way to talk about "how expensive is this method" that does not depend on whose laptop it runs on. That is what complexity analysis gives us.

Why not just time it with a stopwatch?

You could measure your program with a clock. People do this, and it is useful. But as a way of comparing algorithms it falls apart:

• Your friend's laptop is faster than yours, so the same code gives different numbers.
• Running the same program twice gives slightly different times.
• A slow algorithm on a fast machine can beat a fast algorithm on a slow machine — for small inputs. Then the inputs grow, and it loses badly.

What we actually want to know is: as the input grows, how fast does the work grow? That question has an answer independent of hardware.

Counting operations

Instead of seconds, count steps. Look at this:

marks = [88, 72, 95, 61, 79]

total = 0
for m in marks:
    total = total + m

print("Sum:", total)
print("Count of items looked at:", len(marks))

The loop body runs once per element. If the list has n elements, the loop does about n additions. Double the list, double the work. That is a straight-line relationship, and we call it linear.

Now compare with this:

marks = [88, 72, 95, 61, 79]

print("First mark:", marks[0])
print("Length:", len(marks))

These lines do the same amount of work whether the list has 5 items or 5 crore items. Python does not walk through the list to fetch marks[0]. That is constant work.

Two different growth patterns. That is the whole idea.

Big-O notation

Big-O is shorthand for "grows roughly like". We write:

• O(1) — constant. The work does not depend on input size.
• O(n) — linear. Double the input, double the work.
• O(n^2) — quadratic. Double the input, four times the work.
• O(log n) — logarithmic. Double the input, the work goes up by only one step.

When we write Big-O we deliberately throw away two things:

Constant factors. An algorithm doing 3n steps and one doing n steps are both O(n). Yes, one is three times slower, but they scale the same way, and constants depend on machine details anyway.

Lower-order terms. An algorithm doing n^2 + 5n + 100 steps is O(n^2). When n is 1,00,000, the n^2 part is a hundred thousand times bigger than the 5n part. The small terms stop mattering.

The four you will meet most

O(1) — constant. Reading arr[7]. Adding two numbers. Pushing onto a stack. Looking up a key in a Python dictionary (usually).

O(log n) — logarithmic. Binary search in a sorted list. Each step throws away half the remaining data. To search 10 lakh sorted items you need about 20 comparisons, because 2^20 is roughly 10 lakh.

O(n) — linear. Scanning a list to find the maximum. Counting how many students passed. Summing an array. You must touch every element at least once, so you cannot do better than O(n) for these.

O(n^2) — quadratic. Comparing every pair of items. Bubble sort. Checking whether any two students have the same roll number using two nested loops.

Here is the growth, made concrete:

Look at the last row. An O(n) method needs ten lakh steps — a fraction of a second. An O(n^2) method needs a million million steps — that is hours, possibly days. Same problem, same computer, different method.

Seeing the difference yourself

def count_linear(n):
    steps = 0
    for i in range(n):
        steps += 1
    return steps

def count_quadratic(n):
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1
    return steps

for n in [10, 50, 100, 200]:
    print("n =", n,
          "| linear steps:", count_linear(n),
          "| quadratic steps:", count_quadratic(n))

Run it. The linear column grows the way n grows. The quadratic column explodes. Nothing about the code is badly written — the shape of the work is different.

Space complexity

The same idea, applied to memory instead of time. Ask: how much extra memory does this algorithm need as n grows?

nums = [4, 9, 1, 7, 3]

# O(1) extra space: a couple of variables, regardless of list size
largest = nums[0]
for x in nums:
    if x > largest:
        largest = x
print("Largest (O(1) extra space):", largest)

# O(n) extra space: we build a whole new list as big as the input
doubled = []
for x in nums:
    doubled.append(x * 2)
print("Doubled (O(n) extra space):", doubled)

The first block keeps one variable no matter how long the list is — O(1) space. The second builds a new list of the same size — O(n) space. Both scan the list once, so both are O(n) time. Time and space are separate measurements, and often you trade one for the other.

Best, average and worst case

Searching a list for a value:

• Best case: it is the first element. One comparison. O(1).
• Worst case: it is last, or missing. n comparisons. O(n).
• Average case: about n/2 comparisons, which is still O(n).

Unless we say otherwise, Big-O usually refers to the worst case, because that is the guarantee you can rely on.

Common mistakes

Thinking O(n) is always faster than O(n^2). For small inputs the constant factors can dominate, and a simple O(n^2) method may win. Big-O describes behaviour as n grows large, not a promise at n = 8.

Counting loops instead of understanding them. Two loops one after the other is O(n) + O(n) = O(n), not O(n^2). Only nested loops multiply.

Forgetting the cost of built-in operations. Writing if x in my_list inside a loop looks like one line, but in on a list is O(n). That innocent line turns your O(n) loop into O(n^2).

Ignoring space entirely. An algorithm that is fast but copies the input at every step can run out of memory on large data.

Keeping constants in the notation. O(2n) and O(n + 3) are not standard. Write O(n).

Practice

Work through the complexity exercises on the practice page — try labelling small snippets before you look at the answers.