# Thread: Big-Oh notation and a logarithmic function problem

1. ## Big-Oh notation and a logarithmic function problem

I need help with a problem I found in a Discrete Mathematics book.

The problem is:

Prove that the $\lfloor{\log_{2} n}\rfloor + 1$ is $O(\log_{2} n)$ or $\lfloor{\log_{2} n}}\rfloor + 1$ is big-oh of $\log_{2} n$

So according to the definition of Big-O notation we have to show that:

$\lvert{\lfloor \log_{2} {n} \rfloor + 1} \rvert \leq M * \lvert{\log_{2} n}\rvert$

Now what property of logarithm proves that:

$\lvert{\lfloor{\log_{2}n}\rfloor + 1}\rvert \leq M * \lvert{\log_{2}n}\rvert$

From my knowledge I can't find a way to prove this. Can anyone kindly help me with this?

2. ## Re: Big-Oh notation and a logarithmic function problem

Originally Posted by x3bnm
I need help with a problem I found in a Discrete Mathematics book.

The problem is:

Prove that the $\lfloor{\log_{2} n}\rfloor + 1$ is $O(\log_{2} n)$ or $\lfloor{\log_{2} n}}\rfloor + 1$ is big-oh of $\log_{2} n$

So according to the definition of Big-O notation we have to show that:

$\lvert{\lfloor \log_{2} {n} \rfloor + 1} \rvert \leq M * \lvert{\log_{2} n}\rvert$

Now what property of logarithm proves that:

$\lvert{\lfloor{\log_{2}n}\rfloor + 1}\rvert \leq M * \lvert{\log_{2}n}\rvert$

From my knowledge I can't find a way to prove this. Can anyone kindly help me with this?
Say that $\lfloor{\log_{2}n}\rfloor=x$. Then,

$\lvert{\lfloor{x}\rfloor + 1}\rvert \leq M * \lvert{x}\rvert$

$\lvert{\lfloor{x}\rfloor + 1}\rvert \leq \lvert{\lfloor{x}\rfloor + \lfloor{x}\rfloor}\rvert =2\lvert{x}\rvert$

3. ## Re: Big-Oh notation and a logarithmic function problem

Originally Posted by x3bnm
I need help with a problem I found in a Discrete Mathematics book.

The problem is:

Prove that the $\lfloor{\log_{2} n}\rfloor + 1$ is $O(\log_{2} n)$ or $\lfloor{\log_{2} n}}\rfloor + 1$ is big-oh of $\log_{2} n$

So according to the definition of Big-O notation we have to show that:

$\lvert{\lfloor \log_{2} {n} \rfloor + 1} \rvert \leq M * \lvert{\log_{2} n}\rvert$

Now what property of logarithm proves that:

$\lvert{\lfloor{\log_{2}n}\rfloor + 1}\rvert \leq M * \lvert{\log_{2}n}\rvert$

From my knowledge I can't find a way to prove this. Can anyone kindly help me with this?
For $n>2,\ 0<\lfloor \log_2(n) \rfloor \le \log_2(n)$

and: $n>2,\ 1 < \log_2(n)$

and since for $n>2$ everything is positive we have:

$n>2,\ |\lfloor \log_2(n) \rfloor+1| < 2|\log_2(n)|$

and Also.. beat me to it....

CB

4. ## Re: Big-Oh notation and a logarithmic function problem

Thanks Also sprach Zarathustra and CaptainBlack for your help.