Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 3

A preorder is a binary relation that is reflexive and transitive: $a⪯a$, and $a⪯b⪯c$ implies $a⪯c$.

A partial order is a preorder that is also an antisymmetric relation: $a⪯b$ and $b⪯a$ together imply $a=b$.

A linear order, also called a total order, is a partial order in which every two elements are comparable: $a⪯b$ or $b⪯a$ for all $a,b\in A$.

This is the pointwise order on a function space. Each of the three partial order axioms follows from the corresponding axiom in $B$.

For reflexivity, $f(x){⪯}_{B}f(x)$ for every $x$, so $f{⪯}_{\mathcal{F}}f$. For antisymmetry, if $f{⪯}_{\mathcal{F}}g$ and $g{⪯}_{\mathcal{F}}f$, then $f(x)=g(x)$ for every $x\in A$; equality of functions therefore gives $f=g$. For transitivity, if $f{⪯}_{\mathcal{F}}g{⪯}_{\mathcal{F}}h$, then $f(x){⪯}_{B}g(x){⪯}_{B}h(x)$ for every $x$, so $f{⪯}_{\mathcal{F}}h$.

Thus $(\mathcal{F},{⪯}_{\mathcal{F}})$ is a partially ordered set. The argument also covers an empty domain $A$, since then there is exactly one function $A\to B$.

Interpret ${\mathbb{R}}_{+}$ as the strictly positive reals, as in the domain $x>0$ in question 1(e). A bound valid for every $n$ is immediately an eventual bound, by taking $m=0$ (or the least natural number under the other convention).

Conversely, suppose the eventual big O notation bound holds with constants $m,c$. Since $g(j)>0$, all the finitely many ratios $|f(j)|/|g(j)|$ with $j<m$ are finite. Chooseomitting the set of ratios when it is empty. For $n<m$ the definition of $C$ gives $|f(n)|\le C|g(n)|$, and for $n\ge m$ the original bound does so. Hence the two definitions are equivalent for the stated strictly positive codomain.

Strict positivity matters. If ${\mathbb{R}}_{+}$ were instead intended to include zero, an eventual bound need not extend to all indices: $g(0)=0$, $f(0)=1$, and $f(n)=g(n)=1$ for $n\ge 1$ give a counterexample. More generally, extension is possible exactly when each initial zero of $g$ is also a zero of $f$.

Use natural logarithms; the same argument works for any fixed base greater than $1$. The function $\log \log x$ is increasing for $x>1$, since its derivative is $1/(x\log x)>0$. With natural logs the sole negative summand is at $i=2$. Put $C_0=|\log \log 2|$.

For all sufficiently large $n$ with $\log \log n\ge 1$, monotonicity and the triangle inequality giveThese are fixed constants and an eventual bound, provingFor another fixed logarithm base there are still only finitely many negative initial terms, which are absorbed in $C_0$.

For natural logarithms and sufficiently large $n$, take the logarithm of the positive expression:Set $t=\log \log n$. Then $\log n=e^t$. The exponential function grows faster than $t^2$: for example, its power series gives $e^t\ge t^3/6$ for $t>0$, so $t^2/e^t\le 6/t\to 0$. In particular, eventually $(\log \log n{)}^2\le \log n$. Exponentiating yieldsFor logarithms to a fixed base $b>1$, the natural logarithm of the left side is $(\log \log n-\log \log b{)}^2/\log b$, still smaller than $\log n$ eventually. The big O notation conclusion is therefore independent of that base choice.

Unroll the recurrence relation down to its initial condition:ThusIndeed $T(n)/n^2\to 1/2$, so the sharper growth classification is $\Theta (n^2)$ in big theta notation.

Multiplying the recurrence relation by $n$ removes the average:For $n\ge 2$, subtract the same identity at $n-1$:Rearranging gives $T(n)=T(n-1)+2-1/n$. This also holds at $n=1$, because the original recurrence relation gives $T(1)=1$ and $T(0)=0$. Summing the differences therefore yieldsHere $H_n$ is a harmonic number. Since $H_n\le n$, we have $n\le T(n)\le 2n$ for $n\ge 1$, also establishing $\Theta (n)$ in big theta notation.