 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/discrete-mathematics-continuous-mathematics-and-probability/3/a/i/solution

f, g : N \to R

f = O (g) ⟺ \exists C > 0 \exists N \forall n \geq N : ∣ f (n) ∣ \leq C ∣ g (n) ∣.

3^{l o g n} = n^{l o g 3}

. Since

lo g 3 > 1

, for every

n \geq 1

we have

n \leq n^{l o g 3}

. The witnesses

C = 1, N = 1

therefore prove

n = O (3^{l o g n}) .

 New to topics? Read the docs here!