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

Dividing by $n^2$ gives $10^5/n+2\to 2$. Thus the quadratic term controls the growth:The sharper Big theta notation also supplies the requested Big O notation bound.

For $n>0$,Consequently $\boxed{\sqrt{n^6+n^2}=\Theta (n^3),\text{in particular }O(n^3)}$ in Big theta notation and Big O notation.

Here $a,b\ge 2$ are fixed integers. The term $a{b}^n$ has exponential growth, whereas $a{n}^b$ has fixed-degree polynomial growth and $n{b}^a$ is linear. Since a fixed-base exponential eventually dominates every fixed-degree polynomial,Hence the requested Big O notation bound, with its matching lower order, is $\boxed{\Theta (b^n),\text{in particular }O(b^n)}$.

For sufficiently large positive $n$, the logarithm identities giveAfter division by $n{\log }_{2}n$, the right-hand side tends to one. Thus $\boxed{\Theta (n\log n),\text{in particular }O(n\log n)}$ gives the asymptotic order in Big theta notation and Big O notation.