GATE CSE 1996 | Question: 1.11

Question

Which of the following is false?

• A. $100n \log n=O(\frac{n\log n}{100})$

• B. $\sqrt{\log n} = O(\log\log n)$

• C. If $0 < x < y \text{ then } n^x = O\left(n^y\right)$

• D. $2^n \neq O\left(nk\right)$

Comments

its correct only

---

In similar manner, you can check other options. They all are correct except B.

Hence, B is the answer.

---

For B), set $log(n) = x$, so that we get $\sqrt{x} = O(log(x))$. This is clearly false as polynomial functions grow faster than logarithmic functions for large input sizes. So you cannot bound a polynomial function above by a logarithmic function.

Answer 1

• A. $100n \log n=O(\frac{n\log n}{100})$  : Big-$O$ denotes the growth rate of functions and multiplication or division by a constant does not change the growth rate. So, this is TRUE and here $O$ can even be replaced by $\Theta$ or $\Omega$.
• B. $\sqrt{\log n} = O(\log\log n)$  : FALSE. $\sqrt \log n = ({\log n}) ^{0.5}$ grows faster than $\log \log n$ as any positive polynomial function $($including powers between $0-1)$ grows faster than any polylogarithmic function. (Ref: Section 3.2- Logarithms, Cormen). We can also do substitution here, but we must do for at least $2$ large values and ensure it works for any larger $n$ also. 
• C. $0 < x < y \text{ then } n^x = O\left(n^y\right)$ : TRUE since $y$ is always greater than $x$. So, RHS is always greater than LHS.
• D. $2^n \neq O\left(nk\right)$ : TRUE since $k$ is constant. So, for large values of $n$, LHS is much higher than RHS (exponential function always greater than linear).

Only B is FALSE.

Comments

o means O also

---

we take very large value for n

---

Nice explanation.

Answer 2

Answer: B

Comments

implies or equal to?

---

"implies"

---

(Logn)^0.5  grows faster