recategorized by
555 views
1 votes
1 votes

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

  1. $n \: \log a = \Omega (\log ^2 (n)), \text{ where a is a constant >1}$
  2. $n!=\text{O} \big( (\frac{n}{2})^{(\frac{n}{2})} \big)$
  3. $4(n+k)^m = \text{O} (n^m), \text{ where m is a constant >1}$
  4. $n+\log (n) = \Theta (n)$
recategorized by

1 Answer

1 votes
1 votes
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)$
Answer:

Related questions

1 votes
1 votes
1 answer
4
Applied Course asked Jan 16, 2019
504 views
Suppose a radix sort was done on the following set of numbers, in binary i.e,$[11, 10, 3, 14, 12, 2, 8, 15, 2]$. How many passes of counting sort would be performed _____...