Big-O notation — formal definition, mathematical: Question bank

Two pictures to hold in your head first

True or false — justify

5 n^{2} + 100 n = O (n^{2})

True — for

n \geq 1

100 n \leq 100 n^{2}

, so

5 n^{2} + 100 n \leq 105 n^{2}

; the constant

c = 105

absorbs everything and the lower-order term is dominated.

n^{2} = O (n^{3})

True but loose — for

n \geq 1

n^{2} \leq n^{3}

, so

c = 1

works; Big-O is an upper bound, so a function may be

O

of something that grows strictly faster.

n^{3} = O (n^{2})

False —

n^{3} \leq c n^{2}

would force

n \leq c

for all large

n

, impossible for a fixed

c

n \to \infty

f = O (g)

, is it always true that

g = O (f)

False — Big-O is directional like

\leq

, not symmetric;

n = O (n^{2})

holds but

n^{2} = O (n)

does not.

lo g_{2} n = O (lo g_{10} n)

True — logs of different bases differ only by the constant factor

lo g_{2} 10

, which the multiplier

c

absorbs; that is why we write

O (lo g n)

with no base.

2^{n + 1} = O (2^{n})

True —

2^{n + 1} = 2 \cdot 2^{n}

, a constant multiple, so

c = 2, n_{0} = 0

works; adding a constant to an exponent only rescales.

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

False —

2^{2 n} = (2^{n})^{2}

, so the ratio

2^{2 n} / 2^{n} = 2^{n} \to \infty

; no fixed

c

caps it. Doubling the exponent is not a constant factor.

n! = O (2^{n})

False — factorials outgrow every fixed-base exponential; the ratio

n! / 2^{n} \to \infty

, so no constant caps it.

100 = O (1)

True — a constant function is bounded by

c \cdot 1

(take

c = 100

); constants are

O (1)

, the class of "grows not at all."

sin n + 2 = O (1)

True — it oscillates between

1

and

3

, so it is bounded above by

c = 3

times

1

; boundedness, not smoothness, is what

O (1)

needs.

n = O (n lo g n)

True — for

n \geq 3

lo g n \geq 1

, so

n \leq n lo g n

;

c = 1, n_{0} = 3

works (using natural log).

Spot the error

2^{n} = O (n^{100})

because

n^{100}

is a huge polynomial." — where's the flaw?

Size at a fixed

n

is irrelevant; what matters is the limit. As

n \to \infty

2^{n} / n^{100} \to \infty

, so any exponential eventually overtakes any polynomial. False.

3 n + 7 = O (n)

requires

n_{0} = 7

, the smallest threshold that works." — flaw?

The definition needs existence of some

n_{0}

, not the minimal one;

c = 10, n_{0} = 1

also proves it. Any valid pair suffices.

f = O (g)

means

f

and

g

have the same running time." — flaw?

It means

f

grows no faster than

g

, an upper bound; they can differ wildly (e.g.

n = O (n^{2})

). Same-order requires

Θ

, see Big-Theta notation — tight bound.

"I dropped the constant, so

5 n^{2} = O (n^{2})

— but

500000 n^{2}

O (n)

since I dropped

500000

." — flaw?

You may drop the coefficient but not change the power; the constant

c

absorbs

500000

, leaving

n^{2}

, never

n

. Dropping constants ≠ dropping the growth term.

n^{2} + n^{2} = O (n^{4})

by the product rule." — flaw?

That is a sum, not a product; the sum rule gives

O (max (n^{2}, n^{2})) = O (n^{2})

. The product rule (

O (g_{1} g_{2})

) applies only to multiplied factors.

"Since

f (n) \leq c g (n)

can fail at

n = 0

, the claim

f = O (g)

is broken." — flaw?

The bound need only hold for

n \geq n_{0}

; small-

n

violations are exactly what

n_{0}

lets us skip. Failure below the threshold does not disprove anything.

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

, so the sum is a different class." — flaw?

O (2 n) = O (n)

because the factor

2

is absorbed by

c

; the sum of two linear costs is still linear.

Why questions

Why does the definition allow any

c > 0

rather than fixing

c = 1

Because

c

is what lets us ignore machine- and implementation-dependent coefficients; without a free

c

5 n

would not be

O (n)

and the notation would depend on hardware.

Why do we need

n_{0}

at all instead of demanding the bound for all

n

Small inputs behave erratically (setup costs, one algorithm briefly beating another);

n_{0}

lets us focus purely on scaling as

n \to \infty

, which is what we care about. See Limits and infinity (Calculus).

Why must

g (n)

be nonnegative for

n \geq n_{0}

The bound

0 \leq f (n) \leq c g (n)

sandwiches

f

between

0

and

c g

; if

g

went negative,

c g

would too and the inequality would be impossible for any positive cost

f

. Complexity functions count steps, so nonnegativity is natural.

Why is the inequality one-sided (

\leq

) rather than two-sided?

Big-O is only an upper bound; capturing a matching lower bound is the job of Big-Omega notation — lower bound, and both together give Big-Theta notation — tight bound.

Why is

f = O (g)

really an abuse of notation?

O (g)

is a set of functions; the honest statement is

f \in O (g)

. Writing "

=

" tricks people into thinking it is symmetric, which it is not.

Why does the sum rule collapse to the maximum,

O (f) + O (g) = O (max (f, g))

f \leq c_{1} h

and

g \leq c_{2} h

with

h = max (f, g)

, then

f + g \leq (c_{1} + c_{2}) h

; the smaller term is swallowed by the dominant one. See Asymptotic growth rates ordering.

Why can Big-O never distinguish

n

from

2 n

but does distinguish

n

from

n^{2}

2 n = 2 \cdot n

is a constant multiple (absorbed by

c

), whereas

n^{2} / n = n \to \infty

is not bounded by any constant, so the growth shape genuinely differs.

Edge cases

f (n) = 0

for all

n

, is

f = O (g)

for any

g

with

g (n) \geq 0

for all large

n

Yes —

0 \leq 0 \leq c g (n)

holds trivially for any

c > 0

wherever

g

is nonnegative; the zero function is

O

of every nonnegative

g

g = O (g)

(a function big-O of itself)?

Yes — take

c = 1, n_{0} = 0

g \leq 1 \cdot g

; Big-O is reflexive, matching its "

\leq

"-like nature.

Can

g (n) = 0

at some points and still have

f = O (g)

Only if

f

is also

0

wherever

g

is, past

n_{0}

; if

g (n) = 0

but

f (n) > 0

there, then

f \leq c \cdot 0 = 0

fails, so no

c

works.

Is a decreasing function like

f (n) = 1/ n

still

O (1)

Yes — it is bounded above by

1

, so

c = 1

works; Big-O caps growth from above, and a shrinking function is trivially capped.

f = O (g)

and

g = O (f)

, what does that mean?

They bound each other both ways, so they have the same growth order — that is exactly

f = Θ (g)

; see Big-Theta notation — tight bound.

n = o (n^{2})

(little-o) the same claim as

n = O (n^{2})

No — little-o demands the ratio

\to 0

(strictly smaller growth), while Big-O only demands it stay bounded; every

o

is an

O

, but not vice versa. See Little-o and little-omega.

Connections

3.1.01 Big-O notation — formal definition, mathematical (Hinglish)
Big-Omega notation — lower bound
Big-Theta notation — tight bound
Little-o and little-omega
Asymptotic growth rates ordering
Time Complexity vs Space Complexity
Master Theorem
Limits and infinity (Calculus)