Big-O and Complexity Analysis

1. What It Is and Why It Exists

notation describes how the running time (or memory) of an algorithm grows as the input size n grows, ignoring constant factors and lower-order terms. It answers the only scaling question an interviewer cares about: "If the input gets 10x bigger, what happens to your solution?" Without it you can only say "this feels fast" — which is useless when the difference between O(n) and O(n^2) is the difference between passing and timing out on n = 10^5.

The reason we drop constants and keep only the dominant term is that for large n, the highest-order term swamps everything else: 3n^2 + 1000n + 50000 is O(n^2) because once n is large the n^2 term decides the runtime, and hardware/language constants are not portable across machines. is an upper bound on growth rate, so it lets you compare algorithms by shape, not by stopwatch. Interviewers expect you to state complexity out loud while you code, not after.

Quick check

A backend engineer has two sorting implementations for processing user records. Implementation A has a measured runtime of 3n² + 1000n + 50000 operations, and Implementation B runs in 5n² operations. When evaluated using Big-O notation, how do these two implementations compare?

2. Operations and Complexity

The table orders common growth rates from slower to faster growth. A complexity class does not itself specify an average or worst case; those depend on the algorithm and its input.

Class	Name	Typical source of this bound
`O(1)`	Constant	Array indexing; hash lookup on average; dynamic-array stack push amortized
`O(log n)`	Logarithmic	Binary search, balanced binary-search-tree operations, heap push/pop
`O(n)`	Linear	Single pass, linear scan
`O(n log n)`	Linearithmic	Merge sort, heapsort
`O(n^2)`	Quadratic	Nested loop over all pairs
`O(2^n)`	Exponential	Visiting every subset, before accounting for copying each result
`O(n!)`	Factorial	Visiting every permutation, before accounting for copying each result

Rules interviewers probe: drop constants (O(2n) = O(n)), drop lower-order terms (O(n^2 + n) = O(n^2)), sequential code adds (O(n) + O(n) = O(n)), nested loops multiply (O(n) * O(m) = O(nm)). Distinguish best / average / worst case — interviewers almost always mean worst case unless you say otherwise; quicksort is the classic "average O(n log n), worst O(n^2)" trap. Space complexity counts extra memory you allocate (auxiliary), and depth counts.

Compare how work grows

Growth classes compare shapes, not measured seconds; nested work multiplies while sequential work adds.

Binary search grows logarithmically because each pass halves the range.

Text version

Binary search grows logarithmically because each pass halves the range.
A linear scan grows with the input size.
Merge sort adds a logarithmic factor to linear growth.
All-pairs work grows quadratically, so its curve soon leaves this chart.
Visiting every subset grows exponentially, before counting the cost of copying each result.
Each curve shows its value at the same input size, sixteen.
Two to the n already reaches about sixty-five thousand, while n squared is only two hundred fifty-six.
Two nested scans of the full input multiply to n squared, while two sequential scans add to twice n.
Drop constant factors and lower-order terms when naming the growth class.
Quicksort takes n times log n on average, but n squared in the worst case.

Quick check

A backend service has two sequential steps: first, it scans a list of n user records (O(n)), then for each record it performs a hash lookup to check permissions (O(1) per lookup, O(n) total). What is the overall time complexity of this service operation?

3. Implementation

The examples below illustrate the analysis: count how many times the innermost statement runs as a function of n = len(nums). The binary-search example assumes ascending sorted input. For recursive algorithms, T(n) denotes the running time on size n; merge sort makes two calls on half-sized inputs and spends O(n) merging at each level, giving O(n log n) over O(log n) levels. The final stub records that recurrence rather than implementing the sort.

# O(n): the loop body runs n times, each iteration is O(1).
def total(nums):
    s = 0
    for x in nums:        # n iterations
        s += x            # O(1) work
    return s              # -> O(n) time, O(1) extra space

# O(n^2): for each of n elements, an inner loop does up to n work.
def has_duplicate_pair(nums):
    for i in range(len(nums)):          # n
        for j in range(i + 1, len(nums)):  # ~n
            if nums[i] == nums[j]:      # O(1)
                return True
    return False                        # -> O(n^2) time, O(1) extra space

# O(log n): the search space halves every iteration.
def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                     # runs log2(n) times
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1                           # -> O(log n) time, O(1) extra space

# Recursion: solve T(n) by the recurrence. Master-theorem shortcut for
# T(n) = a*T(n/b) + f(n): merge sort is T(n) = 2T(n/2) + O(n) = O(n log n).
def merge_sort_cost(n):
    # 2 subcalls on n/2, plus O(n) merge -> O(n log n) total.
    pass

In an interview you do not "reach for a library" here — you narrate the analysis: count loop iterations, multiply nested loops, write the recurrence for , and state the bound before the interviewer asks.

Count the passes in binary search

Binary search on eight sorted values narrows the range from eight cells to one and finds the target on the fourth pass.

Search eight sorted numbers for nine, starting with the full range.

Text version

Search eight sorted numbers for nine, starting with the full range.
The first midpoint is index three, which holds five, less than nine.
The lower bound moves to four, leaving four cells.
The second midpoint holds seven, so the lower bound rises again.
The third midpoint holds eight, leaving only the last cell.
The fourth midpoint holds nine, which matches the target.
Return index seven after four passes through the loop.
Halving gives logarithmic time, while the fixed set of variables uses constant extra space.

Quick check

A backend service has a function that checks whether any two user IDs in a list are duplicates by comparing every pair. A second function retrieves a user ID from a sorted list by repeatedly halving the search space. If the list contains n user IDs, what are the time complexities of the duplicate-check function and the retrieval function, respectively?

4. When to Reach for It

Always, before you finish coding — state the time and space complexity of every solution unprompted.
When n can reach 10^5, an O(n^2) full scan is usually too slow; look for O(n log n) or better. A time-limit exceeded (TLE) result depends on the runtime limit, language, and work per operation, so growth rates guide an estimate rather than guarantee a pass.
Around n = 20, visiting 2^n states may be practical: 2^20 is about one million. Enumerating 20! permutations is far larger and generally infeasible; distinguish exponential subset search from factorial permutation search.
When asked "can you do better?" → compare your current class to the next class down and identify what structure (hash, sort, ) closes the gap.

Use constraints to estimate the work

At an input size of 100,000, compare quadratic and linearithmic growth estimates, then account for the runtime limit and work per operation.

The input can reach one hundred thousand elements.

Text version

The input can reach one hundred thousand elements.
Squaring that input size gives ten billion growth units.
The base-two log of one hundred thousand is about seventeen, so n times log n is about one point seven million.
The quadratic estimate is about six thousand times larger.
Growth counts are not timings, because the time limit, the language and the work per operation all matter.
Quadratic work is usually too slow here, so aim for n times log n or better.

Quick check

You are building a backend API endpoint that processes a list of up to 100,000 user records. Your current implementation sorts and queries this list using a nested loop, resulting in O(n²) time complexity. During load testing, the endpoint consistently times out. Which of the following best explains the problem and the appropriate target complexity?

5. Common Pitfalls

Reporting best case as the answer. Saying " is O(1) if we get lucky" — interviewers want worst case. Default to worst case.
Ignoring hidden cost of built-ins. x in a_list is O(n), s = s + char in a loop is O(n^2) (string is immutable, rebuilt each time), slicing a[1:] is O(n). Misjudging these silently turns an O(n) analysis into O(n^2).
Forgetting space. A n deep is O(n) auxiliary space even with no explicit data structure — say so.
Multiplying when you should add. Two sequential loops are O(n), not O(n^2); two nested loops each doing n iterations give O(n^2). If their lengths differ or shrink, count the actual total iterations. Misreading control flow is the most common error.
Treating O(n log n) and O(n) as interchangeable. They differ enough to matter at scale; do not hand-wave the log n.

Quick check

A backend developer writes the following Python function to build a query string from a list of parameters: def build_query(params): # params has n items result = '' for p in params: result = result + p return result What is the actual time complexity of this function, and why?

6. Interview Cheat Sheet

" is the asymptotic upper bound on growth; I drop constants and lower-order terms and report worst case unless I say otherwise."
"Sequential blocks add, nested loops multiply, and is analyzed by its recurrence — merge sort's T(n) = 2T(n/2) + O(n) gives O(n log n)."
"I read the constraints first: n <= 10^5 rules out O(n^2); n <= 20 invites an exponential search."
"Space complexity is the auxiliary memory I allocate, and depth counts toward it."

Follow-ups:

"What's the difference between , Big-Θ, and Big-Ω?" — O is an upper bound, Ω a lower bound, Θ a tight bound (both). In interviews people say "O" but usually mean a tight worst-case bound.
"Your solution is O(n^2). Can you do better?" — Identify the repeated work; replace a nested scan with a hash map (O(n)) or sort + (O(n log n)).
"Is O(2n) worse than O(n)?" — No; constants are dropped, they are the same class. Different constants can matter in practice but not in Big-O.

Tier 1 · Foundations

Complexity

Linear Structures

Hierarchical Structures

Tier 2 · Patterns

Tier 3 · Dynamic Programming

1. What It Is and Why It Exists

2. Operations and Complexity

3. Implementation

4. When to Reach for It

5. Common Pitfalls

6. Interview Cheat Sheet

Reading

On this page

My notes

Glossary history