GATE CSE 2001 | Question: 1.16

Question

Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct?

• A. $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$
• B. $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$
• C. $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$
• D. $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$

Comments

@vishalshrm539

if it is  $\log n^{10}$ then you can do 10 logn but it is not so

---

https://www.youtube.com/watch?time_continue=1&v=g_rNpqWJH4M&feature=emb_logo

---

good and simple one thanks

Answer 1

Reference:Solution of Arjun Sir

Case-I

$f(n)=n^{2} logn$ 

take $n=2^{10}$  So, $f(n)=2^{20} log2^{10}$  

$f(n)=2^{20} $ *10 $

and $g(n)= n (logn)^{10}$ 

take $n=2^{10}$  So, $g(n)= 2^{10}(log2^{10})^{10}$

$g(n)= 2^{10}* 10^{10}$

Case-II

And now take one more value 

take $n=2^{256}$ 

o, $f(n)=2^{512} log2^{256}$  

$f(n)=2^{512} $ *256 $

and $g(n)= n (logn)^{10}$ 

take $n=2^{256}$  So, $g(n)= 2^{256}(log2^{256})^{10}$

$g(n)= 2^{256}* 256^{10}$

Now, main problem is how to check which one is bigger than other.

Just do one simple thing divide each other 

like in case-I , if you'll divide f(n)/g(n) 

f(n)/g(n) = $2^{20} $ *10  / $2^{10}$ * $10^{10}$

f(n)/g(n) = $2^{10} $ *10  / $10^{10}$

f(n)/g(n) = 10240 / $10^{10}$

So, here f(n)< g(n)  , f(n) = O(g(n))

 

Now Case-II,

f(n)/g(n) = $2^{512} $ *256  / $2^{256}$ * $256^{10}$

f(n)/g(n) = $2^{256} $ *256  / $256^{10}$

Here, you can simply use Scientific calculator during GATE exam, and you will see quotient is >0.

So, here f(n)> g(n)  , g(n) = O(f(n)) and you can find n where f(n) always greater than g(n)

So, Option B

Answer 2

f(n) = n2logn; g(n) = n(logn)10
Cancel nlogn from f(n), g(n)
f(n) = n; g(n) = (logn)9
n is too large than (logn)9
So f(n)! = O(g(n)) and g(n) = O(f(n))

So option B

Answer 3

ans is A.

for n=2 : f(n)=4, g(n)=2

for n=3 : f(n)=14, g(n)=300

Comments

For asymptotic notations, you should always check for large values of n.