Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 3 / a

For functions $f,g:\mathbb{N}\to \mathbb{R}$, big O notation meansUsing the natural logarithm and exponential function, $3^{\log n}=n^{\log 3}$. Since $\log 3>1$, for every $n\ge 1$ we have $n\le n^{\log 3}$. The witnesses $C=1,N=1$ therefore prove

For $n\ge 1$, $\log 3<2$ implies $3^{\log n}=n^{\log 3}\le n^2$, and also $n\le n^2$. ConsequentlyThe definition of big O notation holds with $C=4,N=1$:

Suppose the definition of big O notation held with constants $C>0,N$. Choose an odd integer $n>\max (C,N)$. At this input, $f(n)=n$ and $g(n)=1$, so the required inequality would be $n\le C$, a contradiction. ThusThe infinitely many even inputs, where $f(n)/g(n)=1/n$, cannot repair the failure on odd inputs because the bound must hold for every sufficiently large input.

A direct mathematical induction proves $0\le F_n\le 2^n$. The base cases $F_0=0\le 1$ and $F_1=1\le 2$ hold. If the bound holds at $n-1$ and $n$, then the Fibonacci recurrence givesThus the definition of big O notation holds with $C=1$, proving