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 / iv / Solution

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.