What Is Time Complexity? The Concept Every Interview Tests

Find the number 7 in a sorted list of a million numbers.

Option one: start at index 0 and check each one. Option two: jump to the middle, decide whether 7 is in the left half or right half, and repeat. Both work. One takes up to a million steps. The other takes at most twenty.

That gap, a million versus twenty, is what time complexity measures. And it is also exactly why your interviewer's eyes light up when you mention it.

Your Code Has Two Costs

Every algorithm costs you something. Time is one. Memory is the other.

Time complexity answers a specific question: as input grows, how does runtime grow? Not "does this run in 0.4 seconds on my laptop", but "if I double the input, does runtime double, square, or barely change?"

The answer doesn't depend on your CPU, your language, or whether your laptop fan sounds like a hairdryer. It's a mathematical property of the algorithm. Two engineers on completely different hardware get the same complexity class for the same algorithm.

That portability is the whole point.

Big-O Is Just a Name for Growth Rate

Time complexity is almost always expressed in Big-O notation. You'll see O(n), O(log n), O(n²), and so on.

The "O" stands for "order of," and the expression inside describes how the algorithm scales. The variable n almost always means "the size of your input."

Big-O is deliberately approximate. It drops constants and lower-order terms. An algorithm that does 3n + 50 operations is still O(n), because as n grows into the millions, the 3 and the 50 stop mattering. You're describing the shape of the growth curve, not the exact step count.

That's why two O(n) algorithms can feel different at small n but converge at large n. The notation isn't lying. It's just zoomed way out.

For a deeper look at the formal definition, Big-O Notation covers how to analyze any loop and extract the complexity class.

Why Not Just Benchmark It?

Because benchmarks are a lie. A useful lie, but still.

Benchmarks tell you how fast something runs right now, on this machine, with this input size. They don't tell you what happens at 10x or 1000x. A quadratic algorithm can beat a linear one at n = 100. At n = 100,000 it isn't close. At n = 1,000,000 you might as well go make coffee and come back.

Production systems don't run on your test input. They run on data you haven't seen yet, at volumes you didn't have when you first shipped. Time complexity predicts behavior at scale where benchmarks can't reach.

In an interview, there's another reason: the interviewer can't run your code. They need to hear you reason. "This is O(n²) but I can get it to O(n) with a hash set" is the kind of sentence that changes an outcome.

The Six Classes You Actually Need

Here are the complexity classes that cover 95% of coding interviews, ordered from slowest-growing to fastest-growing.

Complexity	Name	Example
O(1)	Constant	Array index access, hash map lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Single loop through an array
O(n log n)	Linearithmic	Merge sort, heap sort
O(n²)	Quadratic	Nested loops
O(2^n)	Exponential	Brute-force subset enumeration

The growth difference is massive. At n = 1,000:

O(log n): roughly 10 operations
O(n): 1,000 operations
O(n²): 1,000,000 operations
O(2^n): a number with 301 digits

That last one is not rhetorical. 2^1,000 exceeds the estimated number of atoms in the observable universe. You are not running that in any reasonable time. You are not running that in any unreasonable time either. You are not running that.

Complexity class growth curves showing O(1), O(log n), O(n), O(n log n), O(n²), and O(2^n)

Six complexity classes, one graph. Notice how O(2^n) immediately disappears off the top of the chart. This is not a bug in the diagram.

One Problem, Three Solutions

Take "find a duplicate." Same task, three complexity levels.

O(n²): compare everything against everything

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

n elements times n checks = n² operations. At n = 10,000 that's 100 million comparisons. Fine for your unit test. Not fine for anything a real user would actually do.

O(n log n): sort first

def has_duplicate(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Sorting is O(n log n). The single loop is O(n). When you chain operations in sequence, keep the dominant term. Total: O(n log n).

O(n): trade space for time

def has_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

One pass. Each hash set operation is O(1). This is the classic time-space tradeoff: faster runtime, more memory.

Three solutions, three growth curves. Knowing these distinctions is what lets you defend your choice in an interview and then improve it when the interviewer inevitably asks "can you do better?"

How to Read Time Complexity Off Your Code

Three rules cover most interview problems, and once they click you'll start seeing complexity everywhere, including on your own awful old code.

Loops multiply. A single loop over n elements is O(n). Two nested loops over n elements each is O(n²).

# O(n)
for i in range(n):
    process(i)

# O(n²), the interview villain
for i in range(n):
    for j in range(n):
        compare(i, j)

Sequential blocks add, then drop the lower-order term. Sort in O(n log n), then loop once in O(n), and you have O(n log n + n) = O(n log n). The O(n) just... vanishes. Like it was never there.

Halving is logarithmic. Any algorithm that discards half the remaining input at each step is O(log n). Binary search eliminates half the candidates per iteration.

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

A billion-element sorted array needs at most 30 binary search steps. Thirty. That's O(log n) in practice, and it's why anyone who has binary search seared into their brain feels slightly smug at the grocery store.

Recursion Changes the Calculation

Loops are straightforward. Recursive algorithms need a different approach, and they catch people off guard.

Runtime depends on two things: how many recursive calls you make, and how much work each one does. Merge sort calls itself twice on half the input, then does O(n) work to merge. There are O(log n) levels of splitting, each doing O(n) total work. Product: O(n log n).

Naively computing Fibonacci is O(2^n), because without caching you recompute the same subproblems exponentially. Memoize them and the same algorithm becomes O(n). Same code, same structure. One change makes it go from "heat death of the universe" to "instant."

The structure of the recursion tree is everything.

Recursion Time Complexity covers the full toolkit, including the Master Theorem and how to analyze any recurrence.

When Constants Matter

Big-O hides constants, which trips people up early on.

O(n) doesn't mean "fast." An algorithm with a 10,000x constant factor will get beaten by a clean O(n) implementation at any practical input size, even though both are technically "O(n)." When two algorithms share the same complexity class, constants and cache behavior decide the winner.

When they differ by a full class, the class wins at any non-trivial scale. Use complexity class to eliminate options, then use benchmarks to choose between the survivors.

Think of it as a two-round tournament. Big-O is the bracket. Benchmarks are the tiebreaker.

What Interviewers Actually Score

When an interviewer asks for your complexity, they're running two tests simultaneously.

Correct computation means knowing that your nested loop is O(n²), your binary search is O(log n), your hash map lookup is O(1) amortized. This is table stakes.

Tradeoff reasoning is where you actually score. Sorting once in O(n log n) to enable twenty O(log n) binary searches might be the right call. An extra pass can turn O(n²) into O(n). A hash set trades memory for time.

Every interview problem has at least one complexity improvement buried inside it. The brute force usually works. The optimal solution is often one insight away. Interviewers want to see you find that gap, explain why your solution lands where it does, and articulate what you'd give up to go faster.

Five Coding Interview Time Complexity Floors shows how this plays out on real problems. For how time trades against memory, Time and Space Complexity covers the full picture.

Practice Saying It Out Loud

Knowing complexity is one skill. Explaining it under pressure is another.

Interviewers want to hear the reasoning: "I sort in O(n log n), then each binary search is O(log n), and with q queries total it's O((n + q) log n)." That sentence is expected. Silence after writing correct code leaves a dimension unscored, and a confused interviewer staring at your code trying to figure out if you know what you wrote.

If that verbal walkthrough feels unnatural, the gap is real and trainable. SpaceComplexity runs voice-based mock interviews with rubric-level feedback on exactly this: does your complexity analysis hold up in real time, or does it fall apart when someone asks you to justify it?

Key Takeaways

Time complexity describes how runtime grows as input grows, independent of hardware or language.
Big-O captures the dominant growth term, dropping constants and lower-order terms.
The six classes to know: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n).
Three rules cover most code: loops multiply, sequential blocks add (keep the dominant term), halving is logarithmic.
Benchmarks measure one data point. Complexity predicts behavior at any scale.
In interviews, correct computation plus tradeoff reasoning is the full answer.