 Failure of unrestricted Big O composition

ID: failure-of-unrestricted-big-o-composition

From

f_{1} = O (g_{1})

and

f_{2} = O (g_{2})

one cannot generally deduce

f_{2} \circ f_{1} = O (g_{2} \circ g_{1})

. For

f_{1} (n) = 2 n

g_{1} (n) = n

and

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

, the two premises hold, but the ratio of the compositions is

2^{n}

, which is unbounded. A constant scaling of an inner argument can change the growth order after an exponential function is applied.

 New to topics? Read the docs here!