# Why $\left\lceil lgn \right\rceil <lgn+1\le 2lgn\quad for\quad all\quad n\ge 2$

I have some confusion about 3.2-4 in CLRS. Here is the question :

Is the function $\left\lceil \log { n } \right\rceil !$ polynomially bounded? Is the function $\left\lceil \log { \log { n } } \right\rceil !$ polynomially bounded?

There is a point I can't understand.Why $\left\lceil lgn \right\rceil <lgn+1\le 2lgn\quad for\quad all\quad n\ge 2$? I even draw a graph in desmos.

In the graph, I find it should be $n\ge 1.414$ instead of $n\ge 2$. If $n\ge2$, there will never be $\left\lceil lgn \right\rceil =2lgn$.

• The only connection to computer science here is that the purely mathematical inequality was stated by a computer scientist, so I'm voting to close as off-topic. Also, if something's true for all $n\geq \sqrt{2}$, it's certainly true for all $n\geq 2$, so what's the issue? Note that the statement is "It is true for all $n\geq 2$", not "It is true for all $n\geq 2$ and false for all $n<2$." – David Richerby Sep 1 '17 at 12:12
• @DavidRicherby If $n\ge2$, there will never be $\left\lceil lgn \right\rceil =2lgn$. This is $\Theta$ of definition, $n\ge { n }_{ 0 },\quad 0\le { c }_{ 1 }g\left( n \right) \le f\left( n \right) \le { c }_{ 2 }g\left( n \right)$. – Boris Sep 1 '17 at 12:34
• So what? The statement is "$f(n)\leq g(n)$ for all $n\geq 2$", not "$f(n)\leq g(n)$ for all $n\geq 2$ and $f(n)=g(n)$ for some value of $n\geq 2$". If $x$ is greater than $y$, it's certainly greater than or equal to $y$. – David Richerby Sep 1 '17 at 12:37

$\lceil \log n\rceil = \Theta(\log n)$ (or $\lceil \log n\rceil \in \Theta(\log n)$) means that there exist 2 constants $c_1 > 0, c_2>0$ such that
• $\lceil \log n\rceil \geq c_1 \cdot \log n$ for sufficiently large $n$
• $\lceil \log n\rceil \leq c_2 \cdot \log n$ for sufficiently large $n$
The first case is trivial, just pick $c_1=1$ and $\lceil \log n\rceil \geq \log n$ holds for sufficiently large $n$. [Condition 1 satisfied]
For the second case, if you choose $c_2=2$, you have that $\lceil \log n\rceil \leq 2 \cdot \log n$ for sufficiently large $n$. [Condition 2 satisfied]
Note: It does not matter the value of smallest possible $n$ such that the inequality holds, it is enough that for sufficiently large $n$ it holds. If it was $"\forall n \geq 1000"$ nothing would have changed.