Big O in plain words

Complexity analysis Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

Each call counts its inner steps. What does this print?

Python 3.13
def steps(n: int) -> tuple[int, int]:
    one = sum(1 for _ in range(n))
    two = sum(1 for _ in range(n) for _ in range(n))
    return one, two

a, b = steps(10)
c, d = steps(20)
print(c // a, d // b)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 2 4

Right: doubling n doubles the linear count and quadruples the quadratic count.

Growth ratios like these are what Big O summarises, which is why constant factors drop out.

Why not the others?
  • B 2 2. The nested loop grows with n × n, so doubling n multiplies it by 4.
  • C 1 2. Both counts grow when n grows.

30-second answer

Big O describes how the work (or memory) grows as the input gets bigger, ignoring constant factors and smaller terms. O(n) means doubling the input roughly doubles the work; O(n²) means it roughly quadruples. It is an upper bound on growth, so it tells you how an algorithm scales, not its exact speed on small inputs.

Practise saying it · 30 s. No recording, just a timer

Explain Big O to a non-specialist.

Say your answer out loud, then check which of these points you covered:

  • Growth as input grows
  • Drop constants and small terms
  • Upper bound, usually worst case

Deep dive

Constants matter in practice: an O(n) loop doing heavy work per item can lose to an O(n log n) sort on small inputs.

Interviewers usually mean the worst case unless they say average or amortised.

Say the cost in the variables of the question: O(R·C) for a grid, O(V + E) for a graph, O(n + m) for two lists.

Common mistakes

  • Writing O(2n) or O(n + 5); simplify to O(n).
  • Mixing up time and space costs in one answer.

Senior take & follow-ups

State both time and space, in the question's own variables, without being asked.

Follow-up questions

Think of your answer first, then open the hint.

  1. What are Θ and Ω?

    Show hint

    Θ is a tight bound (both upper and lower); Ω is a lower bound. Interviews mostly use O loosely to mean Θ.

  2. When do constants decide?

    Show hint

    Small inputs, hot loops, and cache behaviour; measure when it matters.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.