Time and Space Complexity Explained

Complexity analysis is the measurement tool the rest of algorithms rests on. Without it, "this solution is better" is an opinion. With it, the comparison becomes a fact you can state before writing a line of code.

In this article we will learn what time and space complexity mean, why Big-O notation deliberately throws away constants, how to analyse loops and recursion step by step, what auxiliary space is and why it is the number interviewers usually want, and how to compare two candidate solutions without running either of them.

What is time complexity?

The key word is grows. Time complexity deliberately says nothing about how many milliseconds your code takes on your laptop. That number depends on your CPU, your language, your compiler and what else is running. Growth rate survives all of those.

Why do we drop constants?

Consider two functions that each scan an array once:

def sum_once(nums):
    total = 0
    for n in nums:          # n iterations
        total += n
    return total
 
def sum_twice(nums):
    total = 0
    for n in nums:          # n iterations
        total += n
    for n in nums:          # n more iterations
        total += n
    return total

The second does exactly twice the work, so it is $2n$ operations against $n$. Both are O(n).

This looks like it loses information, and it does — on purpose. The constant 2 is an artifact of this particular implementation. Rewrite it in C and the constant changes. Run it on a faster machine and it changes again. What does not change is that both functions become twice as slow when the array doubles, while an O(n²) function becomes four times slower. That distinction is the one that determines whether your code survives production.

How do you analyse a loop?

Count how many times the loop body runs as a function of the input size.

# O(n) — the loop runs once per element
for i in range(n):
    do_work()
 
# O(n²) — for each of n iterations, an inner loop runs n times
for i in range(n):
    for j in range(n):
        do_work()
 
# O(n²) too — the inner loop averages n/2 iterations, and n × n/2 = n²/2
for i in range(n):
    for j in range(i, n):
        do_work()
 
# O(log n) — i doubles each step, so it reaches n in log₂(n) steps
i = 1
while i < n:
    i *= 2

The third case is the one people get wrong. The inner loop does shrink, but it shrinks linearly, and the sum $n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2}$ is still quadratic. Halving the work does not change the complexity class.

How do you analyse recursion?

Two questions: how many calls are made, and how much work does each call do?

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

Each call spawns two more, and the recursion is n levels deep, so the call tree has roughly $2^n$ nodes. Each node does constant work. That gives O(2ⁿ) — the reason naive Fibonacci becomes unusable around n = 40.

Compare that to 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)      # O(n) work at each level

Each call splits the input in half, so there are $\log n$ levels. Each level does $O(n)$ total merging work. Multiply them: O(n log n).

What is space complexity?

This distinction catches people out. Sorting an array of n items in place is O(1) auxiliary space even though the array occupies O(n) memory, because you did not allocate that array.

The recursion call stack counts. A recursive function n levels deep uses O(n) space even if it allocates nothing, which is why an iterative rewrite is sometimes a genuine memory optimisation rather than a style preference.

The complexity classes you actually meet

The gap between O(n log n) and O(n²) is the one that decides most real systems. At a million elements, one finishes in seconds and the other does not finish.

How to use this in an interview

Work out the complexity before you start coding, and say it out loud. Two things happen. First, you often catch that your intended approach is too slow while it is still cheap to change. Second, the interviewer sees that you reason about cost by default rather than as an afterthought.

A useful heuristic for the target complexity, given the constraints:

Common mistakes

• Confusing best case with average case. Quick sort is O(n log n) on average and O(n²) in the worst case. Both are true and which one you quote matters.
• Forgetting the call stack. Recursion is never O(1) space.
• Treating hash map operations as unconditionally O(1). It is O(1) amortised. A pathological set of keys that all collide degrades it to O(n).
• Adding when you should multiply. Sequential loops add — O(n) + O(n) = O(n). Nested loops multiply — O(n) × O(n) = O(n²).
• Analysing the code you wish you had written. Slicing an array inside a loop is not free; arr[1:] copies.

Conclusion

Time complexity measures how work grows with input; space complexity measures how memory grows. Big-O keeps the dominant term and discards constants, because growth rate is the property that survives changes of machine, language and implementation.

Analyse loops by counting iterations, recursion by multiplying the number of calls by the work per call, and always state the auxiliary space separately. Do this before writing code and most bad approaches eliminate themselves for free.

Next, see how this applies to a concrete technique in the sliding window pattern, where the whole point is turning an O(n²) scan into an O(n) one.