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

  • 1
    $\log_2n=\frac{\log n}{\log 2}$. So by taking $c> \frac{1}{\log 2}$ (for example $c=4$) we have $$\log_2n2011-04-19
  • 0
    Do you mean $\log(2n)$ or $\log_2(n)$?2011-04-19
  • 0
    @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)2011-04-19

3 Answers 3