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$
3
  • 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$
    – user966
    Apr 19, 2011 at 10:46
  • $\begingroup$ Do you mean $\log(2n)$ or $\log_2(n)$? $\endgroup$ Apr 19, 2011 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$
    – user966
    Apr 19, 2011 at 14:17

3 Answers 3

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .