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

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.

---

B

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

why not option A ??

---

because both are not equal since asymptotic symbol not given. LHS is 10000 times greater than RHS.

---

explanation for B is incorrect. For n = 256, LHS = $\sqrt{log256} = \sqrt{8}$ whereas RHS = log(log256) = log(8) = 3

and clearly LHS < RHS is true as $\sqrt{8}$ < 3

To prove such statements wrong, take larger values of n like 2⁶⁴

So, LHS = $\sqrt{log2^{64}} = \sqrt{64} = 8$ 

and RHS = log(log2⁶⁴) = log64 = 6

$\therefore$ LHS $>$ RHS and hence statement B is false.

---

Please update selected answer for option B.

---

sir kindly explain we one thing in option b we can write (logn)^(1/2)

so if we take log then we get  1/2 log logn which is asymptotically equals to "log logn " for large value it is wrong got it but for small value ?? it may give correct value so sir how we resolve this ambiguity need help

---

why can't option c. If we take n= 1/2 and x=1,y=2.

Then n^x= 1/2 and n^y= 1/4. so n^x is greater then n^y.

So, option c can also be false??

---

for option c :-

0 < x < y  --------> 0 < 5 < 10 (suppose)

n^x = O(n^y)

n^x <= n^y * c

xlogn <= ylogn (ignore c here )

now use assumed  value of x and y

5logn <= 10 logn (and now here you put n =2^64)

5 log2⁶⁴<= 10 log2⁶⁴

5*64 log2<= 10*64 log2 (ignore log2​​​​​​​)

384<=640 (so option c is correct )

---

I think there is a( N subscript 0) in the definition of big-O. And we consider N>(N subscript 0).

This should explain it.

---

 

@just_bhavana totally agreeing. 

by the definition of  

$F(n)= O(g(n))                  means f(n) \leq c.g(n)$

 

 

---

@Prashant.sir 

I have a doubt for option A

I think there is a condition for option A to be true.

$100nlogn\leq c.(nlogn)/100$    $\Rightarrow$      $10000.nlogn\leq c.nlogn$

If option A have to be true then $c\geq 10000$ otherwise option A will be false.

Correct me where I'm lagging

---

@MRINMOY_HALDER I think it doesn't matter what the value of c is. As long it's a positive real number, you can take it whatever you want. That's what the definition of big-o is.

---

@toxicdesire but, if I take it c as less than 10000 then LHS is growing faster than RHS which implies option A is false.

---

@MRINMOY_HALDER Does the option explicitly state that c should be less than 10000? 

The definition of big-O states that $f(x) = O(g(x))$ if there exists a constant c such that $f(x) \le c \cdot g(x)$.

Where c is any positive real number.

 

Now, to decide if option 1 is true, one may ask,

Is there a constant c, which is a positive real number, such that

$100 n\cdot \log n \le c \cdot O\left( \frac{n \cdot \log n}{100}\right)$?

Now if the answer to the above question is yes, then well, the option is true, otherwise it's false.

Clearly there exists such constant c, you said it yourself, hence the option is true. 

---

In B), if we take $\log$ in both side

LHS will be $\frac{1}{2}\log \log n$

while RHS will be $\log \log \log n$

So, RHS grows much slower than LHS

---

In optiom C... O is less than equal to but in this it will always be greater than ... Doesn't is should be o

---

For option C:

What if I take value of n between 0 and 1

Let’s say n=0.5 and choose x=2,y=4 then this becomes false

 I think for any value of x and y , n∈(0,1) then it becomes false

!!Correct me If I am wrong

---

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