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

The Big O notation asserts an eventual uniform bound on the size of $f$ by a constant multiple of the size of $g$:The constants $C,n_0$ may depend on the two functions but cannot depend on $n$. Absolute values matter because the stated functions can be real-valued with either sign.

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.

By Big O notation, there are $C_1,C_2>0$ and thresholds after which $f_1(n)\le C_1{g}_1(n)$ and $f_2(n)\le C_2{g}_2(n)$. Choose a common threshold and set $C=\max (C_1,C_2)$. The positivity assumption givesSquaring preserves this inequality, so

First consider powers of four, with a fixed finite base value. For a mathematical induction hypothesis $x_{n/4}\le C(n/4{)}^2$, the recurrence relation givesprovided $C\ge 4/3$ and $C$ also covers the base value.

The allowed integer rounding needs a little more care. Suppose the recurrence relation is applied above fixed base cases, as usual; applying $x_1=4x_1+1$ with a ceiling would not define a positive sequence. For either rounding write $m=\lceil n/4\rceil$ or $m=\lfloor n/4\rfloor$. For $n\ge 6$,Choose $C\ge 16/7$ large enough to bound all finitely many positive-index base values below $6$. By strong induction,This argument starts at $n=6$, so the floor convention's index zero, if used in an earlier base calculation, is absorbed into those fixed initial values. Thus, for either convention with a well-defined finite base,

In modular arithmetic, calculations may be performed after replacing each input by its remainder. For a positive modulus $m$, write $[a{]}_m$ for the remainder in $\{0,\dots ,m-1\}$. ThenEquivalently, if $a\equiv a^{\prime }(\mathrm{mod}m)$ and $b\equiv b^{\prime }(\mathrm{mod}m)$, addition and multiplication give $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$, and a fixed nonnegative integer exponent gives $a^k\equiv (a^{\prime }{)}^k$. One cannot in general reduce the exponent modulo $m$ by this rule.

Use modular arithmetic to keep all intermediate numbers small:Thus $34\cdot 45\cdot 55+89\equiv 2\cdot 5\cdot 7+1=71\equiv 7\equiv -1(\mathrm{mod}8)$. Cubing gives

Repeated squaring computes $a,a^2,a^4,a^8,\dots$ by successively squaring. The binary representation of the exponent specifies which of these values to multiply. For modular exponentiation, reduce after every multiplication; only a number of steps proportional to the logarithm of the exponent is needed.

Here $13\equiv 2(\mathrm{mod}11)$ and $17=16+1$. Successive squares giveTherefore