The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 votes

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?

- $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$
- $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$
- $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$
- $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$

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.

For cross verification of your answer follow whatever Arun ji has mentioned in his answer.

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

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

+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.

+36 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.

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)) ?

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)) ?

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

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.8k
- Digital Logic 2k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.8k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 940
- Others 1.2k
- Admissions 320
- Exam Queries 409
- Tier 1 Placement Questions 17
- Job Queries 52
- Projects 8

34,170 questions

40,847 answers

115,883 comments

39,703 users