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

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.