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 / a

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.