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 n3/2.
Hope this helps!
سؤال
I analyzed an algorithm and for running time I got Θ(n3/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:
Θ(n3/2) = Θ(n · n1/2)
If we compare them we will see that we need to compare the n1/2 and log n. I checked the growth of both and I found that for larger numbers the growth of n1/2 is more than log n. Can I say that n3/2 is asymptotically slower than log n?
المحلول
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 n3/2.
Hope this helps!
نصائح أخرى
If you plot the two, you see that x^(3/2) (black on plot( grows faster than x*log(x) (red on plot): http://fooplot.com/#W3sidHlwZSI6MCwiZXEiOiJ4XigzLzIpIiwiY29sb3IiOiIjMDAwMDAwIn0seyJ0eXBlIjoyLCJlcXgiOiIxNipzaW4ocyleMyIsImVxeSI6IjEzKmNvcyhzKS02KmNvcygyKnMpLTIqY29zKDMqcyktY29zKDQqcykiLCJjb2xvciI6IiNGRjAwMDAiLCJzbWluIjoiLXBpIiwic21heCI6InBpIiwic3N0ZXAiOiIuMDEifSx7InR5cGUiOjAsImVxIjoieCpsb2coeCkiLCJjb2xvciI6IiNCRjFCMUIifSx7InR5cGUiOjEwMDAsIndpbmRvdyI6WyItMjcuNDI0Mjk1Mzg0NjE1MzczIiwiMzguMTExNzA0NjE1Mzg0NTk2IiwiLTcuODczNTk5OTk5OTk5OTk5IiwiMzIuNDU2MjQ2MTUzODQ2MTQiXX1d