0

Which of the following is false?

A) $100n \log{n}=\left(\frac{n \log{n}}{100}\right)$

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

C) If $0<x<y$ then $n^x=O(n^y)$

D) $2^n \neq O(nk)$

What is the correct answer here? I'm sure $C$ and $D$ are right but not able to judge between $A$ and $B$. This is a GATE Exam question.

Community
  • 1
sittian
  • 63
  • 2
  • 10

2 Answers2

1

For B and similar problems with mulitple logs, exponentials, and powers, a trick I've found helpful is taking an extra log or two of both sides.

Instead of asking whether $\sqrt{\log n} = O(\log \log n)$, investigate whether $\frac{1}{2} \log \log n = O( \log \log \log n )$, which is of course false since the right side has more logs and thus will grow asymptotically slower. Thus, the original claim is also false.

CodeLabMaster
  • 753
  • its good method . bt today i posted similar question . where 1.0000001 ^n and n^7/4 now tell which is bigger ? – sittian Jan 13 '17 at 10:21
  • http://math.stackexchange.com/posts/comments/4307906?noredirect=1 – sittian Jan 13 '17 at 10:22
  • Applying this method to that question would frame it as "Which is eventually bigger, $n \log 1.0000001$ or $\frac{7}{4} \log n$?" after you apply some properties of logarithms. Is that clearer? – CodeLabMaster Jan 13 '17 at 10:26
  • little help need . so after implementing ur method second term is bigger ? is it right? – sittian Jan 13 '17 at 10:32
  • $\log n$ grows slower than any power function $n^k$, so the first term is bigger. $\log 1.0000001$ is very small and makes the first term smaller for small $n$, but by the time $n$ is $10^{20}$, the functions reveal their true colors. – CodeLabMaster Jan 13 '17 at 18:58
0

A: You even can compute the ratio of the functions, not only bound it.

B: Is $\;\dfrac{\log n}{\log\log n}\;$ bounded? (Hint: $\log u=_\infty o(u)$).

D: Is $\;\dfrac{2^n}{n^k}\;$ bounded?

Bernard
  • 175,478
  • I think a is right bcz we can write it like n log n = O ( n log n / 10000) and generally we neglect the constant . – sittian Jan 13 '17 at 10:11
  • but wht about b ? its not clear in my thinking ...cn ny one tell better reason else i need to learn it . My calculator also give nearly equal answer in both ones . – sittian Jan 13 '17 at 10:12
  • For A: yes, we can remove the constant factors, by definition. For B: do you know what $;\log u=o(u);$ mean? – Bernard Jan 13 '17 at 10:40
  • ya it means log u < o(u) , not equal it . – sittian Jan 13 '17 at 10:45
  • Not exactly: it means the ratio s $\dfrac{\ln u}u$ tends to $0$ as $u$ tends to $+\infty$. Apply this with $u=\log n$. – Bernard Jan 13 '17 at 10:48