43 votes 43 votes Which of the following is false? $100n \log n=O(\frac{n\log n}{100})$ $\sqrt{\log n} = O(\log\log n)$ If $0 < x < y \text{ then } n^x = O\left(n^y\right)$ $2^n \neq O\left(nk\right)$ Algorithms gate1996 algorithms asymptotic-notation normal + – Kathleen asked Oct 9, 2014 • edited Oct 16, 2017 by Arjun Kathleen 19.8k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply rajan commented Jan 8, 2017 reply Follow Share i think A and B both are wrong bcz for option A no notation is there then we go mathamatically not asymtotically so mathmatically A is also wrong . and for B explanation given below 0 votes 0 votes Chhotu commented Aug 6, 2017 reply Follow Share Please correct option A. Please put ϴ. 0 votes 0 votes sushmita commented Dec 12, 2017 reply Follow Share its correct only 0 votes 0 votes Akash Papnai commented Nov 12, 2019 reply Follow Share In similar manner, you can check other options. They all are correct except B. Hence, B is the answer. 3 votes 3 votes pritishc commented Jul 6, 2020 reply Follow Share 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 votes 1 votes ritiksri8 commented Apr 23 reply Follow Share B 0 votes 0 votes Please log in or register to add a comment.
Best answer 62 votes 62 votes $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$. $\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. $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. $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. Prashant. answered Aug 16, 2016 • edited Aug 15, 2018 by Arjun Prashant. comment Share Follow See all 19 Comments See all 19 19 Comments reply Show 16 previous comments AASTHA CHANDRA commented Jul 15, 2022 reply Follow Share o means O also 0 votes 0 votes AASTHA CHANDRA commented Jul 15, 2022 reply Follow Share we take very large value for n 0 votes 0 votes ananya_23 commented Dec 29, 2023 reply Follow Share Nice explanation. 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 votes Answer: B Rajarshi Sarkar answered Jun 4, 2015 Rajarshi Sarkar comment Share Follow See all 16 Comments See all 16 16 Comments reply Show 13 previous comments srestha commented Jul 26, 2018 reply Follow Share implies or equal to? 0 votes 0 votes Soumya29 commented Jul 26, 2018 reply Follow Share "implies" 0 votes 0 votes Diksha Kiran 1 commented Nov 1, 2018 reply Follow Share (Logn)^0.5 grows faster 0 votes 0 votes Please log in or register to add a comment.