Complexity Analysis (Big-O)

Question 1

A function with a single loop that runs n times, and inside it a nested loop that also runs n times — what is its time complexity?

Accepted Answer

O(n²) — A loop nested inside another loop, each running n times, multiplies to n × n = O(n²).

Question 2

Binary search repeatedly halves the search range. What is its time complexity?

Accepted Answer

O(log n) — Halving the input on each step means the number of steps needed is the number of times you can divide n by 2 before reaching 1 — that's log₂(n), giving O(log n).

Question 3

At n = 20, roughly how many operations does an O(2ⁿ) algorithm perform compared to an O(n²) algorithm?

Accepted Answer

Over 2,000x as many — 2²⁰ ≈ 1,048,576 versus 20² = 400 — over 2,600x more operations. This is the concrete "why exponential is different in kind, not just degree" the interactive chart is meant to make visceral.

Question 4

Why do interviewers care about Big-O even when the input size in a real system might be small?

Accepted Answer

It shows whether you can reason about solution scaling — Big-O is a proxy for a deeper skill: can you reason about scaling behavior before it becomes a production incident. It intentionally ignores constant factors and exact runtime — that's not what it's for.

Question 5

Performing n append operations on a dynamic array takes O(1) amortized per append. What is the TOTAL copy work across all resizes combined?

Accepted Answer

O(n) — resize copies sum to 1+2+4+…+n/2 = O(n) — With geometric doubling, resizes copy 1, 2, 4, 8, …, n/2 elements. That geometric series sums to less than 2n — so total copy work is O(n). Dividing by n operations gives O(1) amortized per append. The critical insight is that cheap appends (O(1) each) vastly outnumber expensive resizes, so the resize cost is spread across all the cheap operations.

Question 6

Merge sort satisfies T(n) = 2T(n/2) + O(n). By the Master Theorem (a=2, b=2, and n^log_b(a) = n^1), which case applies and what is the time complexity?

Accepted Answer

O(n log n) — Master Theorem case 2: log n levels — Case 2 of the Master Theorem applies when f(n) = Θ(n^log_b(a)). Here a=2, b=2, so n^log_2(2) = n^1 = n, and f(n) = n = Θ(n). The solution is T(n) = Θ(n log n). Intuitively: there are log n recursion levels and O(n) merge work at each level, giving n log n total.

Question 7

A hash set of n items offers O(1) average-case lookup but O(n) worst-case. Which scenario causes the worst case?

Accepted Answer

All n keys hash to one bucket (collisions) — If every key produces the same hash value (possible with a poor hash function or crafted adversarial input), all n items land in one bucket — a linked list requiring O(n) traversal per lookup. This is why production hash tables use load-factor limits, randomized seeds, and sometimes cryptographic hashing to defeat adversarial inputs.

Question 8

Θ(n²) is a strictly tighter characterization than O(n²) because…

Accepted Answer

Both upper and lower bound (Θ sandwiches f) — O(f) bounds growth from above (no faster than f); Ω(f) bounds from below (no slower than f); Θ(f) requires both — the function is sandwiched between c₁·f(n) and c₂·f(n) for all large n. An algorithm that is O(n²) could secretly be Θ(n) — Θ pins the exact growth class, providing both an upper and lower bound simultaneously.

Question 9

A recursive function traverses a binary tree of n nodes, calling itself on each subtree. What is the WORST-CASE call-stack depth?

Accepted Answer

O(n) in degenerate trees (linked-list shape) — Call-stack depth equals the longest root-to-leaf path. In a balanced tree this is O(log n). But a degenerate tree — where every node has only a right child, forming a linked list — has n nodes on its single path, giving O(n) stack depth. Stack-overflow bugs in tree recursion often arise from exactly this worst case on unbalanced data.

Question 10

What is the time complexity of the loop: i = n; while i > 1: i = i // 2?

Accepted Answer

O(log n) — i halves each step, so the loop runs ⌊log₂ n⌋ iterations — Each iteration halves i: after k steps, i ≈ n/2^k. The loop ends when n/2^k ≤ 1, i.e. k ≥ log₂ n. The loop body runs exactly ⌊log₂ n⌋ times — O(log n). This halving pattern is the defining signature of logarithmic algorithms and explains why binary search is O(log n).

Name the growth rate

Test your knowledge

A function with a single loop that runs n times, and inside it a nested loop that also runs n times — what is its time complexity?

The short version

In more depth

Big-O and Algorithmic Complexity

Reading the notation

The ladder that matters in practice

Three cases, and why average matters most

Interview Questions

References & Further Reading

Love this visualization?

Complexity class	Operations at n = 10	Growth type
O(1)	1	constant
O(log n)	3.32	logarithmic
O(n)	10	linear
O(n log n)	33.22	linearithmic
O(n²)	100	quadratic
O(2ⁿ)	1,024	exponential