 Solution

ID: 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

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.

 New to topics? Read the docs here!