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

For real-valued functions, use magnitude comparisons. The constants below are independent of $n$.

The statement $f(n)=O(g(n))$ in Big O notation means that some $C>0$ and integer $N$ satisfy $|f(n)|\le C|g(n)|$ for all $n\ge N$. The statement $f(n)=\Omega (g(n))$ in big omega notation means that some $c>0$ and $N$ satisfy $|f(n)|\ge c|g(n)|$ for all $n\ge N$.

Finally, $f(n)=\Theta (g(n))$ in big theta notation means that some $c,C>0$ and $N$ satisfyEquivalently it is both an eventual upper bound and an eventual lower bound. These definitions ignore a finite initial segment; they do not assert pointwise inequalities with constant one.

Suppose first that $f=O(g)$. Choose $C>0$ and $N$ so that $|f(n)|\le C|g(n)|$ for $n\ge N$. There are only finitely many natural numbers below $N$. Because $g(n)\ne 0$ at each of them, all ratios $|f(n)|/|g(n)|$ in this finite prefix are finite. LetThen $|f(n)|\le c|g(n)|$ both in the prefix and in the tail, hence on the entire domain of a function. This proves the finite-prefix extension of a big O bound.

Conversely, a bound valid for every natural number is certainly valid eventually. The purported real constant cannot be negative because $g$ never vanishes; if it is zero, enlarge it to a positive constant. The definition of Big O notation then applies. The nonvanishing assumption is what permits the finite exceptions to be absorbed into one constant.

True. For every integer $n\ge 1$, $n^2\le n^3$ and $1\le n^3$. ThereforeThe constants $C=1097$ and $N=1$ satisfy the definition of Big O notation. Whether the chosen convention for natural numbers includes zero is immaterial to this eventual assertion.

False. Put $r_n=3^n/n^3$ for $n\ge 1$. For $n\ge 4$,Thus $r_n\ge r_4(192/125{)}^{n-4}\to \infty$. No fixed constant can bound $3^n/n^3$ eventually, so $3^n\ne O(n^3)$. This is an explicit comparison of exponential growth with polynomial growth.

True. Rationalization gives, for $n\ge 1$,This lies between zero and $1/4$, so it is $O(1)$ in Big O notation. In fact it converges to $1/4$, rather than to zero. The rationalized form also avoids the catastrophic cancellation of subtracting two nearby large quantities.

True for every fixed $k\ge 0$. Extract $e^n$ from inside the logarithm:Choose an integer $m>k$. The nonnegative terms of the exponential series give $e^n\ge n^m/m!$ for $n>0$, whenceSince $0\le \log (1+u)\le u$ for $u\ge 0$, the displayed expression tends to zero and is therefore $O(1)$. The constant and cutoff may depend on the fixed $k$; no uniform assertion over unbounded $k$ is being made.

False. On the unbounded subsequence of odd positive integers, $f(n)/g(n)=n$. For any proposed constants $C>0,N$, choose an odd $n>\max (C,N)$. Then $|f(n)|=n>C|g(n)|=C$, contradicting the eventual upper bound required by Big O notation. The small ratio on even integers cannot compensate for this failure on infinitely many odd integers.