Question

Show the correctness of the following statements. (a) \(\lg n \in O(n)\) (b) \(n \in O(n \lg n)\) (c) \(n \lg n \in O\left(n^{2}\right)\) (d) \(2^{n} \in \Omega\left(5^{\ln n}\right)\) (c) \(\lg ^{3} n \in o\left(n^{a \cdot 5}\right)\)

Short answer

All given statements are correct. (a) \(\lg n \in O(n)\), (b) \(n \in O(n \lg n)\), (c) \(n \lg n \in O\left(n^{2}\right)\), (d) \(2^{n} \in \Omega\left(5^{\ln n}\right)\), (e) \(\lg ^{3} n \in o\left(n^{a \cdot 5}\right)\)

Step-by-step solution

Verifying Statement a

To check if \(\lg n \in O(n)\), you need to find a constant \(c > 0\) and \(n_{0} > 0\) such that \(0 \leq \lg n \leq cn\) for all \(n > n_{0}\). As since the log function grows slower than the linear function, this can be satisfied by choosing any positive constants. Therefore, the statement is correct.

Verifying Statement b

To check if \(n \in O(n \log n)\) you need to find a constant \(c > 0\) and \(n_{0} > 0\) such that \(0 \leq n \leq cn\log n\) for all \(n > n_{0}\). The left side equals to the right side when \(c=1\) and \(n_{0}=2\), therefore we can state that the statement is correct.

Verifying Statement c

To check if \(n\lg n \in O(n^{2})\), we need to find a constant \(c > 0\) and \(n_{0} > 0\) such that \(0 \leq n\lg n \leq cn^{2}\) for all \(n > n_{0}\). Since the log function grows slower than the quadratic function, this can be satisfied by choosing any positive constants. Therefore, the statement is correct.

Verifying Statement d

To check whether \(2^{n}\) is in Omega \(\left(5^{\log n}\right)\), you can rewrite \(5^{\log n}\) as \(n^{\log5}\). You are looking for a constant \(c > 0\) such that \(0 \leq cn^{\log 5} \leq 2^{n}\) for a sufficiently large \(n\). But as \(n\) increases, \(2^{n}\) grows much faster than \(n^{\log 5}\) and thus the inequality holds for a sufficiently large \(n\). Thus, the statement is correct.

Verifying Statement e

To check whether \(\lg^{3} n\) is in little o of \(n^{a \cdot 5}\), we need to find a constant \(c > 0\) such that \(0 \leq c\lg^{3} n < n^{a \cdot 5}\) as \(n\) goes to infinity, for all real constant \(a\). Since the log function grows much slower than any polynomial function, therefore the statement holds for all real constant \(a\). Hence, the statement is correct.