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.5k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments 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 Mridul Sachan commented Jun 27, 2015 reply Follow Share why (b) is false?? please see the image. 1 votes 1 votes Rajarshi Sarkar commented Jun 27, 2015 reply Follow Share (log n)1/2 is not equal to $\frac{1}{2}$ log(log n). Take a very big number like, n = 21024 Then, while, Hence, B is false. 12 votes 12 votes Aakash Das commented Jul 12, 2016 reply Follow Share Why not (D)? 0 votes 0 votes Rajendra Dangwal commented Dec 8, 2016 reply Follow Share 2n is exponential, whereas nk is polynomial. Exponential growth function is always bigger than the polynomial. So, nk = O(2n) is true but not the reverse. 1 votes 1 votes monanshi commented Apr 13, 2017 reply Follow Share I think the above picture attached by Mridul Sachan is correct. Why (log n)1/2 is not equal to 12 log(log n)? Rajarshi Sarkar @Arjun Sir can you please help? 1 votes 1 votes Prashant. commented Apr 13, 2017 reply Follow Share Why you are doing partiality with RHS , (why not taking log of RHS). Take ${\color{Blue} log}$ both side or don't take. If we take log : Then LHS = $\frac{1}{2} log\left ( logn \right )$ RHS = $log\left ( log\left ( logn \right ) \right )$ 8 votes 8 votes shraddha_gami commented Apr 13, 2017 reply Follow Share ohh..Thanks! I didn't notice that 0 votes 0 votes Prashant. commented Apr 13, 2017 reply Follow Share @shraddha_gami try with 210 then $\sqrt{10}\neq log(10)$ ryt? 0 votes 0 votes shraddha_gami commented Apr 13, 2017 reply Follow Share Yeah! but still i have doubt when to take large values and their are many sums in which even we have to take more than these. 0 votes 0 votes Prashant. commented Apr 13, 2017 reply Follow Share No particular Rule for that, Most of the time we take random value just to disprove the options. 0 votes 0 votes shraddha_gami commented Apr 13, 2017 reply Follow Share Okay! :) 0 votes 0 votes srestha commented Jul 19, 2017 reply Follow Share @monanshi one point I got $\left ( \sqrt{log n} \right )=\Omega \left ( log log n \right )$ but I have doubt about C) and A) If C) is correct it should be $n^{x}=small-o\left ( n^{y} \right )$ As it is strictly grater than x And also doubt about A) how multiplication and division of same values could be equal? It is not given as asymptotic. (only div and mul by 100)right? 0 votes 0 votes Soumya29 commented Jul 26, 2018 reply Follow Share @Srestha. Little-oh implies Big-Oh. 1 votes 1 votes 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.