Analyzing Time and Space Complexity with Big-O

Complexity is about growth, not stopwatch time

Suppose a function receives a list samples of length $n$. The value $n$ is the input size. We ask:

If $n$ becomes much larger, how does the amount of work grow?

We usually model runtime as a count of elementary operations rather than milliseconds. Wall-clock time depends on hardware, Python version, cache behavior, and implementation details. Big-O deliberately ignores those details so that it captures the part that matters when data scales.

Consider:

def mean_energy(samples):
    total = 0.0

    for x in samples:
        total += x * x

    return total / len(samples)

The loop visits every sample once. If there are $n$ samples, it performs roughly $n$ loop-body updates, plus a fixed amount of setup and return work:

where $a$ and $b$ are constants. We write its running time as:

This is linear time. Doubling the number of samples roughly doubles the work.

Now contrast it with a function that compares every frame with every frame:

def total_pair_distance(features):
    total = 0.0
    n = len(features)

    for i in range(n):
        for j in range(n):
            total += abs(features[i] - features[j])

    return total

For every one of the $n$ outer-loop iterations, the inner loop performs $n$ iterations. The loop body therefore runs:

times, so time complexity is:

That distinction is important: a pairwise operation over 1,000 items is about one million comparisons; over 100,000 items, it is about ten billion.

The common growth classes worth recognizing immediately are:

The plotted range is small, but the trend is the point. At tiny $n$, implementation constants can matter more than asymptotic class. At production or interview-scale $n$, the growth rate usually decides whether an approach is viable.

What Big-O simplifies—and what it does not

Big-O describes an asymptotic upper bound: beyond some sufficiently large input size, the work is bounded above by a constant multiple of a function. In interview conversation, saying “the complexity is $O(n^2)$” generally means “$n^2$ is the tightest standard upper bound we have identified.”

Two simplification rules do most of the work.

Drop constant multipliers

If a function makes three complete passes through a list, its operation count may be approximately $3n$. Its Big-O time is still:

Likewise, $1000n$ is $O(n)$. It may be significantly slower in practice than $n$, but both scale linearly.

Keep only the dominant term

For:

the quadratic term eventually dominates:

Do not apply these rules before understanding the structure. First write the work contributed by each block; then simplify.

A useful interview habit is to state your reasoning in this order:

1. “The first loop runs $n$ times.”
2. “The second loop also runs $n$ times, but it is nested.”
3. “So the body executes $n\cdot n$ times.”
4. “Therefore the time complexity is $O(n^2)$.”

That makes your answer auditable rather than a guess based solely on the number of for keywords.

A reliable procedure for analyzing short Python functions

Use this six-step process.

1. Define the input-size variables

A single list usually has length $n$:

def f(items):
    ...

If a function receives two independently sized inputs, use separate variables:

def compare(a, b):
    ...

Let:

Do not assume both have equal length unless the function contract guarantees it.

2. Ignore fixed-size work initially

Assignments, arithmetic on scalar variables, comparisons, and indexing are usually treated as constant-time operations under the normal algorithm-analysis model.

For example:

first = values[0]
limit = 10
return first + limit

is $O(1)$ time, assuming values is nonempty. It does not matter whether the list has 10 items or 10 million: the code performs a fixed amount of work.

A fixed count is still constant:

for _ in range(100_000):
    update_state()

This is $O(1)$ with respect to input size. It may be a poor engineering choice because 100,000 operations are substantial, but the count does not grow when the caller supplies more input.

3. Add sequential blocks

def summarize(values):
    total = 0
    for x in values:
        total += x

    maximum = values[0]
    for x in values:
        if x > maximum:
            maximum = x

    return total, maximum

The first loop costs $n$, and the second costs $n$:

Thus:

Sequential loops add; they do not multiply.

4. Multiply nested dependent loops

def print_pairs(values):
    for x in values:
        for y in values:
            print(x, y)

For each of $n$ choices of x, the inner loop visits $n$ values of y:

So time is $O(n^2)$.

If the collections differ:

def cross_score(queries, candidates):
    for query in queries:
        for candidate in candidates:
            score(query, candidate)

then the correct answer is:

not automatically $O(n^2)$. It becomes $O(n^2)$ only if both inputs are known to have the same size $n$.

5. Check whether a loop shrinks the problem

def reduction_steps(n):
    steps = 0

    while n > 1:
        n //= 2
        steps += 1

    return steps

The successive values are approximately:

After $k$ iterations, the value is about $n/2^k$. The loop ends near 1, so:

which implies:

Therefore the time complexity is:

The base of the logarithm is not written in Big-O because changing bases only introduces a constant factor.

6. Count extra memory separately

After time, ask: what extra storage does the function allocate as the input grows?

Do not count the input itself when reporting auxiliary space. Count new lists, dictionaries, sets, copies, recursion frames, and other storage created by the algorithm.

Time complexity and auxiliary space are different questions

Return to the energy example:

def mean_energy(samples):
    total = 0.0

    for x in samples:
        total += x * x

    return total / len(samples)

It has:

• Time: $O(n)$, because every sample is visited.
• Auxiliary space: $O(1)$, because total and x are a fixed number of scalar variables.

Now consider a function that creates a separate output:

def square_copy(values):
    result = []

    for x in values:
        result.append(x * x)

    return result

It also visits each value once:

But result grows to contain $n$ elements:

If you modify a mutable input in place instead:

def square_in_place(values):
    for i in range(len(values)):
        values[i] = values[i] * values[i]

then:

• Time: $O(n)$
• Auxiliary space: $O(1)$

The input list already exists; the function only uses a fixed number of extra variables.

The output-space convention

Interviewers differ on whether the returned output should count as space. Avoid ambiguity by stating the convention:

“The auxiliary space is $O(1)$, excluding the output. If we count the returned list, total additional storage is $O(n)$.”

For square_copy, that distinction is especially important. For print_pairs, materializing all pairs in a list would require $O(n^2)$ output space—because there are $O(n^2)$ pairs to store.

Code patterns that reward careful counting

The next video works through code examples similar to the ones you will see in Python interviews. Pay particular attention to the distinction between sequential and nested loops, and to the fact that a loop bounded by a fixed constant does not add another $n$ factor.

Here are three cases where simply “counting loops” gives the wrong answer.

Triangular nested loops are still quadratic

def unique_pairs(values):
    pairs = []

    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            pairs.append((values[i], values[j]))

    return pairs

The inner loop does not always run $n$ times:

• for i = 0, it runs $n-1$ times;
• for i = 1, it runs $n-2$ times;
• eventually it runs 0 times.

The total work is:

After dropping constants and lower-order terms:

Avoid saying “there are two loops, therefore $O(n^2)$.” Instead, count iterations. It happens to be quadratic here, but for a reason.

A break changes best case, not necessarily worst case

def contains_negative(values):
    for x in values:
        if x < 0:
            return True
    return False

• Best case: the first value is negative, so $O(1)$.
• Worst case: no negative value exists, or it occurs last, so $O(n)$.

Unless an interviewer asks for best-case behavior, report the usual worst-case complexity:

You can add: “Best case is $O(1)$ because of the early return.”

Recursion may consume stack space

def countdown(n):
    if n == 0:
        return
    countdown(n - 1)

There is one recursive call per decrement:

At the deepest point, there are $n$ active calls on Python’s call stack:

A recursive function may have linear time but nonconstant space even if it does not allocate an explicit list.

Python-specific details worth remembering

Big-O analyzes the code you actually write, not just the loops you see. These operations frequently matter:

A caveat for later: dictionary and set lookup are typically treated as expected $O(1)$, but their behavior rests on hashing assumptions. The next lesson will use that fact carefully for frequency-counting problems.

A compact interview-answer template

When asked for the complexity of a function, give both a conclusion and its basis:

“Let $n$ be the number of input elements. The outer loop runs $n$ times, and the inner loop runs $n$ times for each outer iteration, so the body executes $n^2$ times. Time is $O(n^2)$. The function only stores scalar counters, so auxiliary space is $O(1)$.”

For a function returning a list, add the output convention explicitly:

“Time is $O(n)$. Auxiliary space excluding the returned output is $O(1)$; including the output list, it is $O(n)$.”

Before committing to an answer, run this mental checklist:

• What is $n$, and are there independent sizes such as $m$ and $n$?
• Are loops sequential (add) or nested (often multiply)?
• Does a loop reduce the remaining work by a factor, suggesting $O(\log n)$?
• Does an early exit change the best case only?
• What new storage grows with input size?
• Am I reporting worst-case time unless a different case was requested?

Key takeaways

Big-O is a language for describing how resource use grows with input size. Fixed work is $O(1)$; one full traversal is generally $O(n)$; dependent nested traversals are often $O(n^2)$; and repeated halving yields $O(\log n)$.

For short Python functions, first identify the size variables, then add sequential costs, multiply genuinely nested costs, simplify to the dominant term, and separately count additional memory. Be precise about best versus worst case and about whether reported space includes a materialized output.

Next, you will apply this analysis while using Python dictionaries and sets to solve a frequency-counting problem—an important pattern where a small amount of extra space can replace a costly nested-loop search.