Applied Course | Mock GATE | Test 1 | Question: 56

Question

$\text{O}, \Omega,$ and $\Theta$ denote Big-Oh, Big-Omega and Big-Theta notations respectively. Which of the following statement is not correct?

• A. $n \: \log a = \Omega (\log ^2 (n)), \text{ where a is a constant >1}$
• B. $n!=\text{O} \big( (\frac{n}{2})^{(\frac{n}{2})} \big)$
• C. $4(n+k)^m = \text{O} (n^m), \text{ where m is a constant >1}$
• D. $n+\log (n) = \Theta (n)$

Answer 1

A is correct.
Proving $n \log(a) = \Omega (\log ^2 n)$ is equivalent to proving $\log ^2 n = \text{O}(n) \text{ [a is constant>1]}$
Now, $\log ^2 n = \text{O} (n)$
$\Leftrightarrow 2 \log \log n = \text{O} (\log n) \text{ [taking log on both sides]}$
$\Leftrightarrow \log \log n = \text{O} (\log n)$
which is correct.

B is incorrect.
$\Leftrightarrow (\frac{n}{2}) (\frac{n}{2}+1) (\frac{n}{2}+1) \dots \dots n < n!$
$\Leftrightarrow (\frac{n}{2})^{\frac{n}{2}} < n!$
$\Leftrightarrow n!=(\frac{n}{2})^{\frac{n}{2}}$

C is correct.
Since $U$ and $m$ are constants greatest order term in $= (n+u)^m$ is $n^m$. So $(n+u)^m = n^m$.

D is correct.
$n + \log n < 2n$
$\Leftrightarrow n+ \log (n) = \text{O}(n) \dots (1)$
$n + \log n > W$
$\Leftrightarrow n+ \log (n) = \Omega (n)  \dots (2)$
From (1) and (2) $n + \log (n)  = \Theta (n)$

Comments

While solving B,

I approximated O(${(N/2)}^{N/2}$) to O(${N}^{N}$) .

If we take log on both side of B

LHS =

RHS = O(n log n) 

So, n! = O(${N}^{N}$)

Ref: https://en.wikipedia.org/wiki/Stirling%27s_approximation

Can someone explain why B is inorrect?