Time and Space Complexity — The Scale Lens

Welcome to the training grounds

You are standing at the gates of Dungeon 1, sword in hand, ready to fight The Biryani Token. An old armorer blocks your path.

"Not yet," she says. "First, take this."

She hands you a monocle. The Scale Lens. When you look at any code through it, glowing runes appear: O(1), O(n), O(n²). Every boss card in this quest carries these runes and every interviewer on Earth will ask you to read them.

This article is the full training. By the end you will be able to look at any code, state its time and space complexity out loud and suggest how to improve it. That is exactly the skill interviews test.

Why not just use a stopwatch?

Fair question. Why invent weird notation when you could time the code?

Because a stopwatch lies. The same code runs at different speeds on your laptop, on a server and on your phone. It runs faster the second time because of caching. It depends on the language, the compiler, the weather in the data center.

Interviewers do not care how fast code runs on some machine. They care about one thing:

When the input grows, how does the work grow?

If you double the input, does the work double? Stay the same? Quadruple? That growth pattern is the complexity and it stays true on every machine ever built. That is what the Scale Lens shows.

Big-O in plain words

Big-O notation is how we write that growth pattern. O(n) reads as "order n" and means: the work grows in a straight line with the input. Double the input, roughly double the work.

Three cousins show up in textbooks:

• Big-O (O): an upper bound. "It grows at most this fast." This is what everyone means in practice.
• Big-Omega (Ω): a lower bound. "It grows at least this fast."
• Big-Theta (Θ): a tight bound. "It grows exactly this fast."

Here is the honest truth for interviews: people say Big-O but usually mean the tight bound of the worst case. When an interviewer asks "what's the complexity?", answer with the worst case unless they ask for average or best. If you want a small bonus point, mention it: "Worst case O(n), best case O(1) if we find it at the first index."

The ladder of growth

Every complexity you will ever meet sits somewhere on this ladder. Lower is faster.

Numbers make it real. Assume a computer does about 100 million simple operations per second. Here is how long each complexity takes:

Read that table twice. The gap between O(n log n) and O(n²) is the gap between "2 seconds" and "11 days". This is why interviewers reject the brute force and wait for something better.

Quick intuition for each rung:

• O(1): same work no matter the input. Array index lookup, hash map get, push to a stack.
• O(log n): you cut the problem in half each step. Binary search. Even a billion items need only about 30 halvings.
• O(n): touch every item once. A single loop.
• O(n log n): do a log-sized amount of work for each of n items. Good sorting lives here.
• O(n²): for every item, touch every item. Nested loops over the same input.
• O(2^n): every item doubles the possibilities. Trying all subsets.
• O(n!): every item multiplies the possibilities. Trying all orderings.

The four rules of the Lens

Before reading code, learn the four simplification rules. These are the whole grammar of Big-O.

Rule 1: drop constants

O(2n) becomes O(n). O(n/2) becomes O(n). Two separate loops over the array is still O(n).

Why? Because constants depend on the machine and Big-O only tracks growth shape. A line is a line whether it is steep or shallow.

Rule 2: drop the smaller terms

O(n² + n + 500) becomes O(n²). When n is a million, the n² term is a trillion and the n term is a rounding error. Only the biggest term survives.

Rule 3: different inputs get different variables

This one catches people constantly. If a function takes two arrays of different sizes, you cannot call both n.

def common_items(a, b):
    set_a = set(a)          # O(a)
    return [x for x in b if x in set_a]   # O(b)

This is O(a + b), not O(n). A nested loop over two different arrays is O(a * b), not O(n²). Saying "n squared" here is a classic interview mistake.

Rule 4: worst case by default

An early return might save you on lucky input, but Big-O reports the unlucky day. Linear search is O(n) even though it might find the answer at index 0.

Reading code, pattern by pattern

Now the core skill. You see code, you say the rune. Here is every common shape.

Straight-line code: O(1)

def get_middle(arr):
    mid = len(arr) // 2
    return arr[mid]

No loops, no recursion, work does not depend on n. Constant time. Even 50 lines of plain statements is still O(1).

One loop: O(n)

def find_max(arr):
    best = arr[0]
    for x in arr:
        if x > best:
            best = x
    return best

Touch each element once. Linear.

Two loops in a row: still O(n)

def sum_and_max(arr):
    total = 0
    for x in arr:        # O(n)
        total += x
    best = arr[0]
    for x in arr:        # O(n)
        best = max(best, x)
    return total, best

Loops that run one after another add up: n + n = 2n, drop the constant, O(n). Sequential means add. Nested means multiply. That distinction does most of the work in complexity analysis.

Nested loops: O(n²)

def has_duplicate(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            if i != j and arr[i] == arr[j]:
                return True
    return False

For each of n items you do n steps. Multiply: O(n²).

The triangle trap: still O(n²)

for i in range(n):
    for j in range(i + 1, n):   # inner loop shrinks each time
        ...

The inner loop runs n-1 times, then n-2, then n-3... That sums to roughly n²/2. Drop the constant: still O(n²). A shrinking inner loop does not save you from quadratic.

The halving loop: O(log n)

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Each pass throws away half the remaining items. How many times can you halve n before hitting 1? That is log₂(n). For a million items: about 20 steps. Any loop that multiplies or divides its counter (i *= 2, n //= 2) is logarithmic.

Loop with a log inside: O(n log n)

for x in arr:              # n times
    binary_search(sorted_arr, x)   # log n each

n items, log n work each: O(n log n). Sorting a list also costs O(n log n), so "sort first, then do a linear pass" is O(n log n + n) which simplifies to O(n log n).

Recursion: the recursion tree method

Recursion scares people in interviews. One tool handles nearly all of it: draw the tree of calls, then multiply two numbers.

Total work = number of nodes in the call tree × work done per call.

A fast shortcut for the node count: branches ^ depth. How many recursive calls does each call make (branches) and how deep does it go (depth)?

Example 1: naive Fibonacci

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Each call spawns 2 calls. Depth is about n. Nodes: 2^n. Work per node: constant.

See fib(3) computed twice and fib(2) three times? The tree is full of repeated work. Time: O(2^n). This is why fib(50) never finishes.

Add a cache (memoization) and every distinct input is computed once. There are only n distinct inputs, so time drops to O(n). That single idea is the heart of dynamic programming, waiting for you in Dungeon 12.

Example 2: merge sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)    # merging is O(n)

Each call splits into 2 calls but on half the data, so the depth is only log n. At every level of the tree, the merging work across all calls adds up to n. Levels × work per level: log n × n = O(n log n).

The cheat table for recurrences

You do not need the formal Master Theorem in interviews. Memorize these five shapes:

Amortized time: the strange case of append

Here is a puzzle. A dynamic array (Python list, Java ArrayList) sometimes runs out of room when you append. It then allocates a bigger array and copies everything over, which costs O(n). So is append O(n)?

Technically the worst single append is. But the resize doubles the capacity, so resizes get rarer and rarer as the list grows. Spread the copying cost across all the appends and each one averages out to O(1).

That average-over-a-sequence cost is called amortized time. Say the word in an interview and you sound like you know what you are doing, because you do.

Same story with hash maps: insert and lookup are O(1) on average, O(n) in the pathological worst case when everything collides. In interviews, treat hash operations as O(1) and mention the caveat once if you want the bonus point.

Space complexity: the other rune

Same Big-O language, but now the question is: how much extra memory does the algorithm use as n grows?

Two conventions matter:

• Auxiliary space: only the extra memory you allocate. The input itself is free.
• When interviewers say "space complexity" they almost always mean auxiliary space. If unsure, ask. It is a good look.

The patterns:

def find_max(arr):        # Space: O(1)
    best = arr[0]         # a few variables, no matter how big arr is
    for x in arr:
        best = max(best, x)
    return best

def squares(arr):         # Space: O(n)
    return [x * x for x in arr]   # new list, same size as input

def count_pairs(grid):    # Space: O(n * m)
    seen = [[False] * m for _ in range(n)]   # a whole 2D structure

The sneaky one: recursion uses space

Every active recursive call sits on the call stack and the call stack is memory. Space cost from recursion = maximum depth of the call tree.

def sum_list(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_list(arr, i + 1)

No arrays allocated, looks like O(1) space. Wrong. At the deepest moment there are n stacked calls: O(n) space. This exact question is an interview favorite.

More examples of stack depth:

• Binary search done recursively: depth log n, so O(log n) space. The iterative version is O(1).
• Merge sort: O(n) space (the merge buffers dominate).
• Quicksort: O(log n) average for the stack, sorts in place.
• DFS on a tree: O(h) where h is the tree height. Balanced tree: O(log n). A degenerate chain: O(n).

The cheat sheets

Pin these somewhere. These cover 95 percent of interview follow-up questions.

Data structure operations (typical/average)

Sorting

Graphs

Graph complexities use two variables (Rule 3 in action): V vertices and E edges.

The interview meta-trick: read n, guess the target

Here is a secret that feels like cheating. Competitive programmers use constraints to reverse-engineer the intended solution. When a problem says "n up to 10^5", it is telling you which complexity will pass.

So when a LeetCode problem says n can be 100,000 and your idea is a nested loop, you already know it will time out before you write a line. The constraint told you.

The improvement playbook

The question after "what's the complexity?" is always "can you do better?". Here is the map from slow pattern to faster weapon. Each row is a dungeon in this quest.

In words:

1. Inner loop searching for something? Replace it with a hash map or set. This is the single most common optimization in all of interviewing. O(n²) becomes O(n).
2. Comparing pairs and order does not matter? Sort first, then use two pointers or binary search. O(n²) becomes O(n log n).
3. Recomputing sums of ranges? Prefix sums or a sliding window. Compute once, reuse forever.
4. Recursion solving the same subproblem twice? Cache it. Memoization or bottom-up DP.
5. Only need the top k items? A heap of size k beats sorting everything.
6. Data sorted and you scan it linearly? Binary search instead.

Notice every one of these is a dungeon in the quest. The whole DSA Quest is really one long answer to "can you do better?".

Your script for the interview

When you see code (yours or theirs), run this exact checklist out loud. Interviewers grade the reasoning as much as the answer.

1. Identify the input size. "Let n be the length of the array." If there are two inputs, name both.
2. Walk the structure. Sequential blocks add. Nested loops multiply. Halving is log. Recursion: branches ^ depth, times work per call.
3. Expand hidden costs. Any in list, slice, sort, string concat inside a loop.
4. Keep the biggest term, drop constants. State the worst case.
5. State space too, without being asked. "Time O(n log n), space O(n) for the sorted copy plus O(1) extra." Mentioning the recursion stack unprompted is a strong signal.
6. Offer the trade. "We could get O(n) time by using a hash set at the cost of O(n) space."

Practice saying full sentences: "This is O(n²) time because for each element we scan the rest of the array, and O(1) extra space since we only use two indices."

Boss fight: five drills

Read each snippet, say the time and space complexity out loud, then check the answer. No skipping. This is the actual training.

Drill 1

def mystery(arr):
    n = len(arr)
    total = 0
    for i in range(n):
        for j in range(i, n):
            total += arr[j]
    return total

Drill 2

def mystery(n):
    count = 0
    i = 1
    while i < n:
        count += 1
        i *= 3
    return count

Drill 3

def mystery(words):
    result = []
    for w in words:              # k words
        result.append(sorted(w)) # each word has up to m letters
    return result

Drill 4

def mystery(root):
    if root is None:
        return 0
    return 1 + max(mystery(root.left), mystery(root.right))

Drill 5

def mystery(arr, target):
    for i in range(len(arr)):
        if target - arr[i] in arr:    # careful here
            return True
    return False

How did you do? If you got drill 5, you are ready for the dungeons.

Common traps, one last sweep

A quick rogue's gallery of mistakes that cost people offers:

• Calling two inputs n. Two different arrays are O(a + b) or O(a · b), never O(n²).
• Forgetting the recursion stack in space. "O(1) space" for a recursive function is almost always wrong.
• Trusting library calls. sorted, in, insert(0, ...), slicing, string += in a loop. Expand them all.
• Thinking the shrinking inner loop helps. n²/2 is still O(n²).
• Saying O(n) for hash operations without the word "average". Fine in practice, but know the caveat.
• Confusing O(log n) levels with O(n) work per level. Merge sort is not O(log n). It is O(n log n) because each level does linear work.
• Reporting best case. Big-O answers are worst case unless someone asks otherwise.

What you unlocked

Look through the Scale Lens one more time. Loops, halvings, recursion trees, hidden library costs, the call stack: all of them glow with readable runes now. You can name the complexity of code you have never seen and you know the standard trade to make it faster.

The armorer steps aside. "One more thing," she says. "The first boss guards a stack of 5,000 wedding tokens and the naive fight is O(n²). You know what to do."

Next up: Dungeon 1, Arrays and Hashing, where a hash set turns a 12-million-comparison disaster into a single pass. Go get your biryani.