|
Prove that if $d(n) = \log(n^x)$, where $x$ is a constant greater than zero, then $d(n)$ is $O(\log(n))$. I have attempted this solution but it seems to me that $\log(a) > \log(b$) if $a > b > 0$. Here is my solution: http://i.imgur.com/sicPn.png which is only valid if $0 < x \leq 1$. Can anyone explain to me where my logic is wrong? |
||||
|
|
|
You have a misunderstanding concerning big O notation. We say that $f(n) = O(g(n))$ if there is some constant $C$ such that $f(n) \leq Cg(n)$ for all $n$ (assuming $f(n),g(n) > 0$ for all $n$). You took $C = 1$, but this need not be so. One important advantage of big O notation is that it doesn't care about (multiplicative) constants. |
|||
|
|
