 Solution

ID: 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/i/solution

The logarithm identity

a^{l o g_{b} n} = n^{l o g_{b} a}

rewrites the expression as

n^{l o g_{2} 3}

. Since

3 < 4 = 2^{2}

, we have

lo g_{2} 3 < 2

, and for

n \geq 1

3^{l o g_{2} n} = n^{l o g_{2} 3} \leq n^{2} .

Thus the Big O notation bound holds with

C = 1

True: 3^{l o g_{2} n} = O (n^{2}) .

 New to topics? Read the docs here!