1
$\begingroup$

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:

$\begin{align}\require{cancel} \lim_{n\to\infty}\frac{lgn}{xlgn}&\ge1\\ \lim_{n\to\infty}\frac\infty{x\times\infty}&\ge1\\[5pt] \text{Apply L'Hopital's rule}\\ \lim_{n\to\infty}\frac{\frac1n}{x\times\frac1n}&\ge1\\ \lim_{n\to\infty}\frac1n\times\frac nx&\ge1\\ \lim_{n\to\infty}\frac1{\cancel n}\times\frac{\cancel n}x&\ge1\\ \lim_{n\to\infty}\frac1x&\ge1 \end{align}$

This is only valid if $0 < x \leq 1$. Can anyone explain to me where my logic is wrong?

1 Answers 1

2

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.

  • 0
    Thank you. So if we set c = x, then this holds true.2012-09-29