Big-Oh notation and a logarithmic function problem

**x3bnm** · November 18th 2011, 10:15 AM

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?

**Also sprach Zarathustra** · November 18th 2011, 10:24 AM

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$

**CaptainBlack** · November 18th 2011, 10:28 AM

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

**x3bnm** · November 18th 2011, 12:19 PM

Thanks Also sprach Zarathustra and CaptainBlack for your help.

Thread: Big-Oh notation and a logarithmic function problem

LinkBack

Thread Tools

Display

Big-Oh notation and a logarithmic function problem

Re: Big-Oh notation and a logarithmic function problem

Re: Big-Oh notation and a logarithmic function problem

Re: Big-Oh notation and a logarithmic function problem

Similar Math Help Forum Discussions

logarithmic notation

[SOLVED] Function Notation word problem

Function notation problem

Need Help with Logarithmic function problem???

Logarithmic Function - Performance Problem