Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Comparing Asymptotic growth of function using logarithms of the following Asymptotic function-:
$$F_{1}=n\,\log n $$
$$\,F_{2}=n^{\frac{3}{2}}$$
$$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!
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.
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.
for $\forall n > 4$ we can show that $$ \sqrt{n} > \log{n} \Rightarrow n^{\frac{3}{2}} > n\log{n}$$
