Asymptotic notation proof

46 Views Asked by At

I am trying to proof below but stuck. Any help would be appreciated.


Give an example of functions such that $f(n) > 0$ and $g(n) > 0$ for all natural $n$, and $f(n) \in O(g(n))$,

but $\lg(f(n)) \notin O(\lg(g(n)))$.

1

There are 1 best solutions below

3
On BEST ANSWER

Take $f(n) = 2$ and $g(n) = 2 ^ {\frac{1}{n}}$. Then

$$\frac{f(n)}{g(n)} \to 2$$

$$\frac{\lg{f(n)}}{\lg{g(n)}} = n \to \infty$$

(Assuming $\lg = \log_2$)