 Solution

ID: 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 give

n lo g_{2} (5 n) + lo g_{2} (n^{2}) + 4 n = n lo g_{2} n + (lo g_{2} 5 + 4) n + 2 lo g_{2} n .

After division by

n lo g_{2} n

, the right-hand side tends to one. Thus

Θ (n lo g n), in particular O (n lo g n)

gives the asymptotic order in Big theta notation and Big O notation.

 New to topics? Read the docs here!