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

Table of contents
- Solution 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}) .

 Ancestors (12)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version