1
$\begingroup$

I have the following question:

Is the following statement true or false?

** All logs to base 2

log2n is a memeber of O(log(n))

My attempt:

log2n - clogn <= 0
log2 + logn - clogn <= 0 1 + logn(1-c) <= 0

Now correct me if I'm wrong, but I have to find values for n (variable) and c (constant) which either prove or disprove this...

Generally this seems to be true:

Choose n0 = 2, c = 3 -> TRUE n1 = 3, c = 3 -> TRUE n2 = 4, c = 3 -> TRUE

Therefore, the statement seems true, as logn is increases as n does. But there are also values for which the above statement will never hold:

e.g.

Choose c = 1 evaluates to greater than zero regardless of the increasing value of n.

So I am confused as to whether this is true or false....

$\endgroup$
  • 1
    $\begingroup$ $\log_2n=\frac{\log n}{\log 2}$. So by taking $c> \frac{1}{\log 2}$ (for example $c=4$) we have $$\log_2n<c\log n$$ $\endgroup$ – user9077 Apr 19 '11 at 10:46
  • $\begingroup$ Do you mean $\log(2n)$ or $\log_2(n)$? $\endgroup$ – Zach Langley Apr 19 '11 at 11:50
  • $\begingroup$ @Zach, thanks for pointing out that. After I reread the problem, I think what he meant is to show $\log_2(2n)\in O(\log_2(n))$ (so ignore my answer above) $\endgroup$ – user9077 Apr 19 '11 at 14:17
3
$\begingroup$

To prove $f(n)\in O(\log(n))$ you need to show that (for $n$ large enough), $f(n) \lt c \log(n)$. You get to choose $c$ and the minimum $n$ for which it applies, but it has to be true for all larger $n$. In your case $c=1$ doesn't work, but $c=2$ does. That is fine, you just need one. If we define a new function $g(n)=\log(2n)+10$ and ask whether $g(n) \in O(\log(n))$, you could say that it is, and $c=2$ works here. Somebody could object that $2\log(2)=2 \not\gt \log(2)+10=11$, you can say that is because $n$ isn't large enough. If you take $n \gt 2^{11}, 2\log(n) \gt \log(n)+11=\log(2)+\log(n)+10=\log(2n)+10$

$\endgroup$
3
$\begingroup$

$$\log_2(2n)=\log_2(2)+\log_2(n)\leq \log_2(n)+\log_2(n)=2\log_2(n)$$ for $n\geq 2$.

$\endgroup$
1
$\begingroup$

Let $a>0$ constant. Then:

$\log_a(n) = \frac{\ln(n)}{\ln(a)} \in \mathcal{O}(\ln(n))$

Therefore, all logarithms share one $\mathcal{O}$-class.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.