in Algorithms edited by
19,158 views
43 votes
43 votes

Which of the following is false?

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

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

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

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

in Algorithms edited by
19.2k views

4 Comments

its correct only
0
0

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

Hence, B is the answer.

3
3
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.
1
1

2 Answers

62 votes
62 votes
Best answer
  1. $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$.
  2. $\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. 
  3. $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.
  4. $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.

edited by

4 Comments

o means O also
0
0
we take very large value for n
0
0
Nice explanation.
0
0
7 votes
7 votes
Answer: B

4 Comments

implies or equal to?
0
0
"implies"
0
0
(Logn)^0.5  grows faster
0
0
Answer:

Related questions