---
title: Big O Notation Interview Questions and Answers (2026)
description: The Big O notation and time complexity interview questions that actually come up — from O(1) to O(n!), space complexity, and how to analyse code out loud.
url: https://usegreenroom.app/blog/big-o-notation-time-complexity-interview-questions
last_updated: 2026-06-21
---

← Back to blog

DSA

# Big O notation interview questions

June 21, 2026 · 16 min read

![Big O notation interview questions and answers — a monotone complexity chart from Greenroom, the AI mock interviewer](/assets/blog/big-o-notation-time-complexity-interview-questions-hero.webp)

You've just written a clean, working solution on the whiteboard. The interviewer nods, leans back, and asks the question that sinks more candidates than any bug ever will: *“Great — so what's the time complexity?”* Your code runs. Your logic is right. And yet your mouth goes dry, because you've spent three weeks memorising solutions and roughly zero minutes practising how to **say** an answer to this out loud. This guide covers the **Big O notation interview questions** that actually come up — time complexity, space complexity, the complexity classes from O(1) to O(n!), and how to analyse code on the spot — with a real, speakable answer for each.

## What Big O notation actually measures

**Big O notation** describes how the running time (or memory) of an algorithm grows as the input size grows. It is deliberately *not* a stopwatch. It doesn't tell you an algorithm takes 3 milliseconds; it tells you that if you double the input, the work roughly doubles (O(n)), or quadruples (O(n²)), or barely moves (O(log n)). Interviewers care about this because hardware gets faster every year, but a quadratic algorithm on a big enough input will always lose to a linear one — the *shape* of the growth is what survives.

Formally, Big O is an upper bound on the growth rate. When we say an algorithm is O(n), we mean its work grows *no faster than* linearly with the input, ignoring constant factors and lower-order terms. That “ignoring constants” part is the source of half the follow-up questions, so we'll come back to it. The mental model that lands in interviews: **Big O is about what happens when n gets large**, not about small inputs where constants dominate.

There are three related notations worth knowing by name. **Big O** (O) is the upper bound — the worst case. **Big Omega** (Ω) is the lower bound — the best case. **Big Theta** (Θ) is the tight bound, used when the upper and lower bounds match. In practice, interviewers say “Big O” when they often mean Θ, and that's fine — just don't be thrown when someone asks for the *best*-case complexity of a search and expects Ω(1).

## The complexity classes, from fastest to slowest

Almost every algorithm you'll discuss falls into one of a handful of complexity classes. Knowing them cold — and being able to name an example of each — is the single highest-leverage thing you can do for a **time complexity interview**. Here's the canonical hierarchy, fastest first:

- **O(1) — constant.** The work doesn't depend on input size at all. Accessing an array by index, pushing to a stack, a hash-map lookup. The dream.
- **O(log n) — logarithmic.** Each step throws away half (or some fixed fraction) of the remaining input. Binary search, balanced-tree operations. Doubling the input adds just *one* more step.
- **O(n) — linear.** You touch each element a constant number of times. A single loop, a linear scan, finding the max of an unsorted array.
- **O(n log n) — linearithmic.** The best you can do for a general comparison sort. Merge sort, heapsort, the sort step inside countless other algorithms.
- **O(n²) — quadratic.** A loop inside a loop over the same data. Bubble sort, comparing every pair, naive nested-loop solutions. Fine for n=100, painful for n=100,000.
- **O(2ⁿ) — exponential.** The work doubles with each added element. Naive recursive Fibonacci, generating all subsets, brute-forcing a combination lock.
- **O(n!) — factorial.** Generating all permutations, the brute-force travelling salesman. Effectively un-runnable beyond a dozen or so elements.

The reason this ordering matters so much in an interview is that it's the ruler you measure your own solution against. When you say “this is O(n²), but I think we can get it to O(n) with a hash map,” you've just demonstrated the exact thing the question is testing: that you can reason about cost, not just produce a working answer. The diagram below is the picture every interviewer has in their head when they ask the question — burn it into yours.

![Monotone green Big O complexity chart showing O(1), O(log n), O(n), O(n log n), O(n squared) and O(2 to the n) curves as input size grows](/assets/blog/big-o-notation-time-complexity-interview-questions-diagram.webp)
*How the complexity classes diverge as input grows — flatter curves stay cheap, steeper ones explode. This is the mental picture behind almost every Big O question.*

## Big O notation interview questions and answers

### What's the time complexity of this nested loop?

The classic warm-up. If you see a loop from `0` to `n` with another loop from `0` to `n` inside it, and the inner work is constant, that's **O(n²)** — you do roughly n × n operations. The trap interviewers set: an inner loop that runs from `i` to `n` (not `0` to `n`). That's n + (n-1) + (n-2) + … + 1, which is n(n+1)/2 operations — still **O(n²)**, because we drop the constant ½ and the lower-order term. Say that out loud: “It's the sum 1 through n, which is n-squared-over-two, so O(n²).” That one sentence separates people who memorised “nested loop equals n-squared” from people who actually understand it.

### What's the difference between best, worst, and average case?

Take linear search through an unsorted array. The **best case** is O(1) — the element you want is the very first one. The **worst case** is O(n) — it's the last element, or not present at all. The **average case**, assuming the target is equally likely to be anywhere, is also O(n) (roughly n/2 comparisons, and we drop the constant). Interviewers usually want the *worst case* unless they say otherwise, because that's the guarantee you can make. The place this gets interesting is quicksort: average O(n log n), but worst case O(n²) when the pivot selection is unlucky — a fact good interviewers love to probe.

### Explain time complexity vs space complexity.

**Time complexity** measures how the number of operations grows with input size; **space complexity** measures how the *extra* memory grows. They're often in tension — the most common optimisation in interviews is trading space for time. Counting duplicate characters with a hash set is O(n) time but O(n) space; doing it by comparing every pair is O(n²) time but O(1) space. When you give a complexity answer, give *both*: “This is O(n) time and O(n) space because of the hash map.” Volunteering the space complexity before you're asked is a small, reliable signal of seniority.

### Why do you drop constants and lower-order terms?

Because Big O is about growth *rate*, not exact counts. An algorithm that does `2n + 10` operations and one that does `100n + 3` operations are both O(n) — as n grows toward infinity, the constants and the `+10` become irrelevant noise next to the linear term. This feels wrong the first time you hear it (“but 100n is way slower than 2n!”), and the honest answer is: yes, constants matter in the *real world*, which is why a well-tuned O(n log n) sort can beat a sloppy O(n) one on realistic inputs. But for *classifying* and *comparing* algorithms at scale, we standardise by dropping them. Knowing both the rule and its limitation is the complete answer.

### Why is binary search O(log n)?

Because each comparison eliminates half of the remaining candidates. Start with n elements; after one step you have n/2, then n/4, then n/8, and so on. The question “how many times can I halve n before I reach 1?” is exactly the definition of log₂(n). That's why doubling the input size only adds *one* extra step to a binary search — a property that feels almost magical the first time it clicks. The same logarithmic shape shows up in balanced binary search trees, heaps, and any divide-and-conquer that discards a constant fraction each step.

### What is amortized time complexity?

**Amortized complexity** is the average cost per operation across a long sequence of operations, even when individual operations occasionally spike. The canonical example is appending to a dynamic array (a Python `list`, a Java `ArrayList`, a C++ `vector`). Most `append` calls are O(1), but occasionally the array is full and has to resize — allocate a bigger block and copy everything, an O(n) operation. Because resizes happen rarely and the array typically doubles, those expensive copies are “spread out” across all the cheap appends, giving an **amortized O(1)** per append. Interviewers ask this to see whether you understand *why* `append` is considered constant-time despite the occasional expensive call.

### What's the Big O of common data structure operations?

This is the lookup table interviewers expect you to have internalised. For a **hash table**: average O(1) insert, delete, and search — but O(n) worst case if everything collides into one bucket. For a **balanced BST** (or a sorted structure like a `TreeMap`): O(log n) for insert, delete, and search. For a **dynamic array**: O(1) index access and amortized O(1) append, but O(n) to insert or delete in the middle (everything shifts). For a **linked list**: O(1) insert/delete at a known node, but O(n) to find that node. The pattern worth saying out loud: “Hash tables buy you O(1) average lookups at the cost of ordering; balanced trees keep ordering at O(log n).”

### Is an O(n) algorithm always faster than an O(n²) one?

No — and this is a favourite “gotcha”. Big O describes behaviour as n grows *large*. For small inputs, constant factors dominate, and an O(n²) algorithm with a tiny constant can easily beat an O(n) one with a huge constant. This is exactly why real-world sort implementations (like Timsort) fall back to insertion sort — an O(n²) algorithm — for small subarrays: on a handful of elements, its low overhead wins. The grown-up answer is: “Asymptotically O(n) wins, but for small or specific inputs the constants can flip it, so I'd benchmark if it mattered.”

### How do you find the complexity of a recursive function?

Count two things: how many times the function calls itself (the *branching factor*), and how the input shrinks each call (the *depth*). Naive recursive Fibonacci makes two calls and only shrinks the input by one each time, giving roughly 2ⁿ calls — **O(2ⁿ)**. Merge sort makes two calls but each works on *half* the input and does O(n) work to merge, which works out to **O(n log n)**. For the common cases, the Master Theorem formalises this, but in an interview you rarely need it — drawing the recursion tree and counting the work per level is usually enough. (We go deep on this in our [recursion and backtracking interview questions](/blog/recursion-backtracking-interview-questions) guide.)

### What's the space complexity of a recursive function?

Don't forget the call stack. Even a recursive function that allocates no data structures uses O(depth) space, because each pending call sits on the stack until it returns. A recursion that goes n levels deep before hitting the base case is O(n) space, even if it looks like it “uses no memory.” This is why deeply recursive solutions can blow the stack on large inputs where an iterative version wouldn't — a trade-off interviewers love to surface, and a reason `tail-call` optimisation exists in some languages.

## How to analyse complexity out loud

The thing nobody tells you: the **time complexity interview question** isn't really testing whether you can compute O(n²). It's testing whether you can *narrate your reasoning* while you do it. Interviewers want to hear the analysis, not just the verdict. Here's the mental checklist to run, ideally talking the whole time:

![Monotone green checklist titled How to estimate Big O on the spot, listing count the loops, halving means log, sorting is the floor, recursion equals branches to the depth, and drop constants](/assets/blog/big-o-notation-time-complexity-interview-questions-figure.webp)
*The five-step estimate to run out loud before you commit to an answer — say the complexity, then justify it.*

Walk through it like this: “There's one loop over the array, so that's O(n). Inside it I'm doing a hash lookup, which is O(1) average, so the loop stays O(n). I'm not sorting, and there's no recursion. The hash map I built is O(n) space. So overall: O(n) time, O(n) space.” That's a complete, senior-sounding answer — and notice it's almost entirely *narration*. The math was trivial; the communication is the skill.

A few habits that make this land. **State the complexity before you write the code** when you can — “I think we can do this in one pass, O(n)” — then deliver it. **Name the dominant term**: if you sort (O(n log n)) and then do a linear scan (O(n)), the total is O(n log n), because the sort dominates. And **always volunteer space**, because most candidates forget it and you'll stand out by remembering.

## Big O practice: LeetCode, GeeksforGeeks, or talking it out?

Here's the honest landscape. **LeetCode** is excellent for building the pattern library — grind enough problems and you'll start recognising “this is a sliding-window” or “this needs a heap” instantly. But LeetCode quietly trains a dangerous habit: it grades your *code*, silently, with no one asking you to *explain* the complexity. You can solve 300 problems and still freeze when a human says “walk me through the time complexity.” **GeeksforGeeks** and similar question-dumps are great references for the complexity of standard algorithms, but reading “merge sort is O(n log n)” is not the same as being able to *derive* it under pressure.

Then there's the **“ask ChatGPT to quiz me”** approach, which is genuinely useful — it'll generate questions and check your written answers. But it has the same blind spot as a textbook: it's text. The real interview is *spoken*, with follow-ups, while someone watches you think. Reading a correct answer and producing one out loud, live, with your voice slightly shaking, are different motor skills — and only one of them is the one you're actually graded on. That gap, between knowing the answer and being able to say it under mild pressure, is the entire reason mock interviews exist.

This is where [Greenroom](/) is built differently from a problem set. It runs **spoken** mock interviews where an AI interviewer asks you to explain time and space complexity, then asks the follow-up — “why is that log n?”, “can you do better on space?” — exactly like a real interviewer would. You practise the verbal skill that LeetCode, GeeksforGeeks, and a static ChatGPT prompt all quietly skip. Pair it with our guides on [common coding interview mistakes](/blog/common-coding-interview-mistakes) and [talking through code like a senior engineer](/blog/coding-interview-communication-tips).

> **The core truth:** interviewers aren't testing whether you can compute O(n²) — a calculator can do that. They're testing whether you can *reason about cost out loud*, name the trade-offs, and not freeze when asked “why?”. Practise the narration, not just the math.

## Put the complexity classes to work

Memorising the hierarchy is step one; the real skill is reaching for the right complexity *while you design a solution* and explaining your choice. When you can say “the brute force is O(n²), but if I sort first I can use two pointers and get O(n log n), and the sort dominates so that's my answer,” you're no longer reciting Big O — you're using it. That's the level that gets offers. Keep building from here with our [data structures interview questions](/blog/data-structures-interview-questions) and the full [DSA coding interview preparation](/blog/dsa-coding-interview-preparation-india) roadmap.

## Frequently asked questions

### What is Big O notation in simple terms?

Big O notation describes how the running time or memory of an algorithm grows as the input size grows, ignoring constant factors and lower-order terms. It is not a measure of exact speed in seconds; it is a measure of the growth rate. For example, O(n) means the work grows linearly with the input, so doubling the input roughly doubles the work, while O(1) means the work stays constant no matter how big the input gets.

### What are the most common time complexities in interviews?

From fastest to slowest, the ones that come up most are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n squared) quadratic, and O(2 to the n) exponential. You should be able to name a concrete example of each: hash lookup for O(1), binary search for O(log n), a single loop for O(n), merge sort for O(n log n), nested loops for O(n squared), and naive recursive Fibonacci for O(2 to the n).

### What is the difference between time complexity and space complexity?

Time complexity measures how the number of operations grows with input size, while space complexity measures how much extra memory the algorithm needs as the input grows. They are often in tension, because a common optimisation is to trade extra memory for speed. For example, using a hash set to find duplicates is O(n) time but O(n) space, whereas comparing every pair is O(n squared) time but O(1) space. A strong answer always states both.

### Why do we drop constants in Big O notation?

Because Big O describes the growth rate as the input becomes large, not the exact operation count. An algorithm that does 2n operations and one that does 100n operations are both O(n), because as n grows toward infinity the constant multiplier and any lower-order terms become insignificant next to the dominant term. Constants do matter in the real world for performance tuning, but for classifying and comparing algorithms at scale we standardise by dropping them.

### Is an O(n) algorithm always faster than an O(n squared) algorithm?

No. Big O describes behaviour as the input grows large, so for small inputs the constant factors can dominate and an O(n squared) algorithm with a tiny constant can beat an O(n) algorithm with a large constant. This is why real sorting libraries fall back to insertion sort, which is O(n squared), for small subarrays. Asymptotically the O(n) algorithm wins, but for small or specific inputs the constants can flip the result, so you would benchmark if it mattered.

### How do I get better at answering Big O questions in interviews?

Practise explaining complexity out loud, not just computing it on paper. The interview tests whether you can narrate your reasoning and answer follow-up questions like why is that log n, so rehearse saying the analysis verbally. Tools like LeetCode build your pattern library but grade only your code silently, so pair them with spoken mock interviews that ask you to explain time and space complexity and then push back with follow-ups, which is exactly what a real interviewer does.

Big O questions test whether you can reason about cost out loud, under real follow-up questions. [Greenroom](https://usegreenroom.app/) runs spoken coding mock interviews that ask you to explain time and space complexity — and then ask “why?” — with feedback on every answer. Free to start.