The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
1.9k views

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?

  1. $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$
  2. $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$
  3. $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$
  4. $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$
asked in Algorithms by Veteran (59.4k points)
edited by | 1.9k views
0
Here for getting quick answer first do minimization on both the sides then apply log on both the sides.

For cross verification of your answer follow whatever Arun ji has mentioned in his answer.
+2
taking log in all case  is not a good practice .

it sometimes give right answer & sometime give wrong answer

if we take log of n^2  && n^100

both are same according to log

log is not always a deciding factor

i hope it help u
+1

@yankur9

First do minimization on both the sides

4 Answers

+14 votes
Best answer

A more formal approach:

$f(n) = n^2 \log n$

$g(n) = n (\log n)^{10}$

We can use the limit definition of O-notation

http://cse.unl.edu/~choueiry/S06-235/files/Asymptotics-HandoutNoNotes.pdf

$\lim_{n \to \infty } \frac{f(n)}{g(n)} = 0, \implies  f(n) = o(g(n))$
small $o$ implying $f$ is strictly asymptotically lower than $g$. Also by definition, $o \implies O \text{ but } O \not \implies o$.

$\lim_{n\to \infty} \frac{f(n)}{g(n)} = c,  c > 0 \implies f(n) = \Theta(g(n))$

$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty, \implies  f(n) = \omega(g(n))$
small $\omega$ implying $f$ is strictly asymptotically higher than $g$. Also by definition, $\omega \implies \Omega, \text{ but } \Omega \not \implies \omega.$

We can use this to prove the above question

For any $k > 0$

 $\lim_{n \to \infty} \frac{(\log n)^{k}}{ n}$

Applying L'Hopital rule

$= \lim_{n \to \infty} \frac{ k*(\log n)^{k-1}}{ n}$

$= \lim_{n \to \infty} \frac{ k!}{n} = 0$

So $(\log n)^k = o(n)$

Now for large $n$, $n > (\log n)^9$

i.e $n^{2}\log n > n(\log n)^{10}$

So $n(\log n )^{10} = o(n^{2}\log n)$

Or

$n(\log n )^{10} = O(n^{2}\log n)$

and

$O(n^{2}\log n) \neq n(\log n )^{10}$

Option B.

answered by Active (1k points)
selected by
+1
Impressive ..... Bt for exam purpose taking a big N value will be more effective ... Dont mind ....
+39 votes
  $f(n)$ $g(n)$
$n = 2^{10}$ $10 \ast 2^{10} \ast 2^{10}$ $2^{10} \ast 10^{10}$
$n = 2^{256}$ $256 \ast 2^{256} \ast 2^{256}$ $2^{256} \ast 256^{10}$

So, as $n$ is going larger, $f(n)$ is overtaking $g(n)$ and the growth rate of $f$ is faster than that of $g$. So, $g(n) = O(f(n))$ and $f(n) \neq O(g(n))$.

B choice. 

answered by Veteran (348k points)
edited by
0
If we calculate log(f(n)) and log(g(n)) then we get

log(f(n))= 2*log(n)+log(log(n))= O(log(n));

log(g(n))= log(n)+10*log(log(n))=O(log(n));

Can we say that f(n)=O(g(n)) and g(n)=O(f(n)) ?
0
the answer should be D right?
+2
Taking log is not a proper method -- it works for some and fails for others.
0

ok sir thank you, and can u please reply to my question in TOC , i really have doubt in understanding the way to approach it thank you!https://gateoverflow.in/1994/gate2014-2-35

0
@Arjun Sir .Great , taking large values of n is probably the best way to solve such questions in gate , isnt it ?
0

But sir then how to decide what to apply log or not when as you had used log  here

https://gateoverflow.in/664/gate2000-2-17

+1 vote
g(n) = O (f (n))

n (logn)^10 <= C* n^2 logn

c is stand for any constant value, it satisfy one condition of option b so by this way you can get answer ..
answered by Active (3.3k points)
–5 votes
ans is A.

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

for n=3 : f(n)=14, g(n)=300
answered by Loyal (8.3k points)
+6
For asymptotic notations, you should always check for large values of n.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,171 questions
43,624 answers
124,024 comments
42,893 users