函数的渐近分析

Question

我有如下函数证明其时间复杂度小于等于O(xlogx)

f(x) =xlogx+3logx2

我需要一些帮助来解决这个问题。

Answer 1

给定，

   f(x) = xlogx+3logx^2
        = xlogx+6logx   // since log (a^b) = b log a

我们知道，f(x) = O(g(x))，如果 | f(x) | <= M。 | g(x) |, 其中M为正实数.

因此，对于 M>=7 且 x 在实数正范围内变化，

M . x log x >= x log x + 6 log x
            >= (x+6) log x.

f(x) = x log x + 3log x^2 
     = O(x log x).