-1
$\begingroup$

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?

Here is the official answer: enter image description here

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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$." $\endgroup$ – David Richerby Sep 1 '17 at 12:12
  • $\begingroup$ @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)$. $\endgroup$ – Boris Sep 1 '17 at 12:34
  • $\begingroup$ 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$. $\endgroup$ – David Richerby Sep 1 '17 at 12:37
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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