# Comparing Asymptotic growth of function using logarithms .

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

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

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.

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

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.

• 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 Oct 19, 2017 at 14:15
• 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. Oct 19, 2017 at 14:21
• thank you for your explanaton Oct 19, 2017 at 14:48

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