Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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....

share|improve this question
1  
$\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$$ –  user9077 Apr 19 '11 at 10:46
    
Do you mean $\log(2n)$ or $\log_2(n)$? –  Zach Langley Apr 19 '11 at 11:50
    
@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) –  user9077 Apr 19 '11 at 14:17
add comment

3 Answers 3

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$

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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