Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics / 2 / b

The logarithm identity $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ rewrites the expression as $n^{{\log }_{2}3}$. Since $3<4=2^2$, we have ${\log }_{2}3<2$, and for $n\ge 1$,Thus the Big O notation bound holds with $C=1$:

The logarithm laws giveFor $n\ge 2$, both $n\le n{\log }_{2}n$ and ${\log }_{2}n\le n{\log }_{2}n$. The expression is therefore at most $(3+{\log }_{2}5)n{\log }_{2}n$. ConsequentlyThe Big O notation concerns eventual behaviour; the zero value of $n{\log }_{2}n$ at $n=1$ is irrelevant.

Divide by the proposed comparison function $2^n$:The ratio is unbounded, so no constant in the definition of Big O notation can work:

The exponential function eventually grows faster than the fixed polynomial. A direct justification uses the ratio $r_n=4^n/n^4$:For all sufficiently large $n$, this ratio exceeds $2$, so $r_n$ grows without bound. The proposed Big O notation bound is therefore impossible:

Treat $a,b$ as fixed positive integers. For $n\ge 1$, $n^2+a\le (1+a)n^2$. Raising this inequality to the positive power $b$ givesThe factor $(1+a{)}^b$ is independent of $n$, as required by Big O notation. HenceA bound uniform over varying $a,b$ is not what the notation here asserts.