1
$\begingroup$

Question

Comparing Asymptotic growth of function using logarithms of the following Asymptotic function-:

$$F_{1}=n\,\log n $$

$$\,F_{2}=n^{\frac{3}{2}}$$

My Approach

$$F_{1}=e^{\log (n\,\log n)}=e^{\log n +\,\log \log n} $$

$$F_{2}=e^{\log (n^{\frac{3}{2}})}=e^{{{\frac{3}{2}} \times\log (n)}}=e^{{k \times\log (n)}} \text{where k=some constant} $$

now i am confused that $F_{2}>F_{1}$.

Is it true?

Please help me out!

$\endgroup$
1
  • $\begingroup$ $\log n <\sqrt n$. In fact, $\log n$ is quasi equivalent to $n^0$. $\endgroup$
    – user65203
    Oct 19, 2017 at 14:11

3 Answers 3

1
$\begingroup$

If $n$ is a number of $b$ bits, $n\log n$ has $b+\log b$ bits, while $n^{3/2}$ has $b+b/2$ bits.

The second function grows faster.

$\endgroup$
2
  • $\begingroup$ makes sense and you are correct , but my point is that we can consider $\frac{2}{3}$ as contant $k$ ,can't we? $\endgroup$
    – laura
    Oct 19, 2017 at 14:35
  • 1
    $\begingroup$ @laura: what else do you want it to be ??? $\endgroup$
    – user65203
    Oct 19, 2017 at 15:46
1
$\begingroup$

My approach would be to assume the inequality $n\log n<n^{\frac32}$ (assuming $n$ to be arbitrarily large), then manipulate it into something more apparent to verify or disprove it.

$$n\log n<n^{\frac32}\\\to\log n<n^{\frac12}\\\to n<e^{n^\frac12}.$$

It is obvious that this inequality is a true statement, thus $n\log n$ is less than $n^\frac32$.


The error you seem to make in simplifying $F_1$ and $F_2$ is not realizing that you can alter them both algebraically to get simpler expressions. You seem to instead try to alter $F_1$ and $F_2$ each alone into more manageable expressions, which, in this case, won't work.

$\endgroup$
3
  • $\begingroup$ thank you for your approach , but i know this approach .I too use it by giving larger values(in power of 2) say $2^{65,536}$ fot easy calculation to compare the function , but actually i is not a good approach.Good approach are to convert functions into simpler parts and then compare $\endgroup$
    – laura
    Oct 19, 2017 at 14:15
  • $\begingroup$ I am still simplifying them, however in the form of an inequality. This allows me to get rid of the $\log\log n$ one gets when simplifying them alone. $\endgroup$ Oct 19, 2017 at 14:21
  • $\begingroup$ thank you for your explanaton $\endgroup$
    – laura
    Oct 19, 2017 at 14:48
0
$\begingroup$

for $\forall n > 4$ we can show that $$ \sqrt{n} > \log{n} \Rightarrow n^{\frac{3}{2}} > n\log{n}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.