Can I say that a Θ(n^3/2)-time algorithm is asymptotically slower than an Θ(n log n)-time algorithm?

Question

I analyzed an algorithm and for running time I got Θ(n^3/2). Now I want to compare it with Θ(n log n) to see if it is asymptotically faster or slower, for that I did this:

Θ(n^3/2) = Θ(n · n^1/2)

If we compare them we will see that we need to compare the n^1/2 and log n. I checked the growth of both and I found that for larger numbers the growth of n^1/2 is more than log n. Can I say that n^3/2 is asymptotically slower than log n?

Answer 1

Yes, you can. For any ε > 0, log n = o(n^ε) (that's little-o, by the way), so the log function grows asymptotically slower than any positive power of n. Therefore, n log n grows asymptotically slower than n^3/2.

Hope this helps!

Answer 2

You can prove it yourself by applying L'Hôpital's rule:

This might also help.