Common complexities — O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!): Question bank

Before we start, one shared vocabulary reminder so no symbol is unearned:

$n$ = the size of the input (how many items you feed the algorithm).
$T (n)$ = the step count — roughly how many basic operations run for that input.
$O (\cdot)$ = an upper bound on growth for large $n$ , with constants and smaller terms dropped (see 3.1.01-Big-O-Notation).

True or false — justify

TF — "An algorithm that is

O (n^{2})

can never be faster than one that is

O (n)

False. Big-O describes growth for large

n

only; it hides constant factors, so an

O (n^{2})

routine with a tiny constant can beat an

O (n)

one with a huge constant for small

n

TF — "

O (2 n)

and

O (n)

describe the same class."

True. The constant

2

is dropped in Big-O, so

O (2 n) = O (n)

; both grow linearly and only differ by a fixed multiplier that asymptotics ignore.

TF — "

O (lo g_{2} n)

and

O (lo g_{10} n)

are different complexity classes."

False.

lo g_{b} n = \frac{lo g _{2} n}{lo g _{2} b}

, so changing base is just multiplying by a constant — Big-O drops it, and both are simply

O (lo g n)

TF — "If the input doubles and the runtime also doubles, the algorithm is

O (n)

True. Runtime scaling in direct proportion to input is the defining signature of linear growth,

T (2 n) \approx 2 T (n)

TF — "If the input doubles and the runtime only goes up by a constant amount, the algorithm is

O (lo g n)

True. Doubling

n

adds exactly one halving step (

lo g_{2} 2 n = lo g_{2} n + 1

), so the extra cost is one constant chunk — the hallmark of logarithmic work.

TF — "Every recursive algorithm is exponential."

False. Recursion's cost depends on the recurrence: Merge-Sort is

T (n) = 2 T (n /2) + c n = O (n lo g n)

, Binary-Search is

T (n) = T (n /2) + c = O (lo g n)

— both recursive, neither exponential.

TF — "

O (n!)

is just a slightly slower version of

O (2^{n})

False.

n!

is a product of

n

factors, most exceeding

2

, so it overtakes

2^{n}

from

n = 4

and pulls away hugely — at

n = 20

n! \approx 2.4 \times 1 0^{18}

2^{n} \approx 1 0^{6}

, a different and worse class.

TF — "Big-O tells you the exact running time in seconds."

False. Big-O is a growth rate, not a wall-clock time; actual seconds depend on hardware, language, and hidden constants that Big-O deliberately discards.

Spot the error

Error — "Two loops one after the other, each running

n

times, so it's

O (n^{2})

The error is multiplying sequential loops. Loops in sequence add:

O (n) + O (n) = O (2 n) = O (n)

; only nested loops multiply.

Error — "This while-loop subtracts

1

from

n

each step, so it's

O (lo g n)

Wrong signature. Subtracting a constant gives

O (n)

iterations; logarithmic requires dividing by a constant factor each step, not subtracting.

Error — "The inner loop runs from

i

n

, so on average it's half as much work, making it

O (n \cdot \frac{n}{2}) = O (\frac{n ^{2}}{2})

, which is better than

O (n^{2})

The

\frac{1}{2}

is a constant and gets dropped:

O (\frac{n ^{2}}{2}) = O (n^{2})

. A triangular loop is the same class as a full nested loop.

Error — "A hash-table lookup is always

O (1)

That is the average case; worst-case (many collisions) can degrade to

O (n)

. See 3.1.03-Best-Worst-Average-Case — the guarantee depends on which case you mean.

Error — "Naive recursive Fibonacci is

O (n)

because there are

n

levels of recursion."

Counting levels ignores branching: each call spawns two, giving a recurrence

T (n) = T (n - 1) + T (n - 2) + c

that grows like

O (2^{n})

— memoizing it (see Dynamic-Programming) is what brings it to

O (n)

Error — "

O (n^{3})

matrix multiplication has three nested loops, so tripling the matrix size triples the runtime."

Tripling

n

multiplies runtime by

3^{3} = 27

, not

3

. With three nested loops each running

n

times, work scales as

n^{3}

Error — "Since

O (n lo g n)

contains a log, it's slower than

O (n^{2})

Reversed.

lo g n

grows far slower than

n

, so

n lo g n ≪ n^{2}

; the linearithmic class sits below quadratic on the ladder.

Why questions

Why do we drop lower-order terms like the

+ n

\frac{n ( n + 1 )}{2}

For large

n

the

n^{2}

term dwarfs the linear

n

term, so it alone decides the growth rate; keeping smaller terms adds no information about how the work explodes.

Why is dividing the problem by a constant factor the "signature" of

O (lo g n)

Because after

k

divisions by

2

you have

n / 2^{k}

items; setting that to

1

gives

k = lo g_{2} n

, so the number of steps is logarithmic in the starting size — see the derivation behind Recurrence-Relations.

Why doesn't the base of the logarithm affect the Big-O class?

Any two bases differ only by the constant factor

\frac{1}{l o g _{2} b}

, and Big-O ignores constant multipliers, so all logarithmic growth collapses into one class

O (lo g n)

Why does

O (2^{n})

arise so naturally from "take-or-skip" decisions?

Each of the

n

items independently has

2

choices, so the number of combinations is

2 \times 2 \times \dots = 2^{n}

; enumerating them all is inherently exponential.

Why can the Master-Theorem hand you

O (n lo g n)

for merge sort without unrolling the whole tree?

It matches

T (n) = 2 T (n /2) + c n

to a known pattern where the per-level work

c n

is constant across all

lo g_{2} n

levels, immediately yielding

c n lo g_{2} n

Why are

O (2^{n})

and

O (n!)

algorithms called "intractable" for large

n

Their step counts grow so fast that even at

1 0^{9}

operations per second the runtime exceeds human timescales for modest

n

(e.g.

n = 20

factorial ≈ 77 years), which is why problems needing them are studied under NP-Completeness.

Why does

n!

overtake

2^{n}

specifically from

n = 4

Both are products of

n

factors, but

n!

's factors (

1, 2, 3, \dots, n

) start exceeding

2

from the third onward, so their product first surpasses

2^{n}

once enough

> 2

factors accumulate — at

n = 4

24 > 16

Edge cases

Edge — "What is the complexity of a loop that runs

n

times but each iteration also loops

n

times — except when

n = 0

Still

O (n^{2})

; the empty case

n = 0

does zero work, but Big-O describes the trend as

n \to \infty

, not the trivial base case.

Edge — "Is an algorithm that does exactly

1000000

operations regardless of

n

really

O (1)

Yes. A fixed, bounded number of operations — however large the constant — is constant time, because it does not grow with

n

at all.

Edge — "For

n = 1

, binary search and linear search both finish in one step — so are they the same complexity?"

No. Complexity is about the growth trend as

n

increases; agreement at a single tiny input says nothing about

O (lo g n)

O (n)

behaviour for large

n

Edge — "A nested loop where the inner loop runs a fixed

100

times regardless of

i

— is that

O (n^{2})

No, it's

O (n)

; the inner loop's count doesn't depend on

n

, so it's a constant factor (

100 n

) that reduces to linear.

Edge — "At

n = 10

, which is bigger,

n^{2}

2^{n}

, and does that change the ordering on the ladder?"

2^{n} = 1024

beats

n^{2} = 100

, and it does not change the ordering — exponential crossed quadratic near

n \approx 4

and stays above forever after.

Edge — "If constants don't matter, can I ignore them when choosing between two real implementations?"

Only for large

n

; for small inputs the hidden constants dominate, so an

O (n^{2})

insertion sort can beat an

O (n lo g n)

merge sort below roughly

n \approx 20

— always profile small cases.

Recall One-line self-test

Say aloud the full ladder from fastest to slowest, then name the signature in code for each of $O (1)$ , $O (lo g n)$ , $O (n)$ , $O (n lo g n)$ , $O (n^{2})$ , $O (2^{n})$ . Answer ::: $1 < lo g n < n < n lo g n < n^{2} < n^{3} < 2^{n} < n!$ ; signatures: constant = no loop over data; log = divide by a factor each step; linear = one pass; linearithmic = $lo g$ passes each linear (or divide-and-merge); quadratic = nested loop; exponential = binary take/skip branching.