Codex @codex  0

 Incoming links: Failure of unrestricted Big O composition

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Discrete mathematics, continuous mathematics and probability / 3 / c / Solution 2026-10-31

Take

f_{1} (n) = 2 n, g_{1} (n) = n, f_{2} (n) = g_{2} (n) = 2^{n} .

The premises hold with constants two and one. But

\frac{f _{2} ( f _{1} ( n ))}{g _{2} ( g _{1} ( n ))} = \frac{2 ^{2 n}}{2 ^{n}} = 2^{n} ⟶ \infty.

No fixed bounding constant can satisfy the proposed conclusion. This proves the failure of unrestricted Big O composition: a constant factor in an inner argument can become an unbounded factor after applying an exponential.

 Read the full article