O(n ^ 2)大于O((n ^ 2)logn)

Question

O(n ^ 2)是否大于O(n ^ 2 log n)？
如是 ？怎么样 ？
我们能有一个简单的例子.
此外,
下面的代码的复杂性是什么.

int unknown(int n){
   int i,j,k=0;
   for(i=n/2;i<=n;i++){
     for(j=2;j<=n;j=j * 2){
         k =k + n/2;
     }
  }
return k;
}

什么是回报值k的复杂性？

Answer 1

O(n^2)是一个子集的O((n^2) * log(n)),因此,首先是"好",很容易看到,因为log(n)是增函数,用它乘以东西,你得到一个"高"功能,则原来的(f(n) <= f(n) * log(n)每个增加非负f和n>2)

您给出的代码捕捉是O(nlog(n)),因为内循环重复log(n)每个外循环迭代次数,外循环重复n/2次 - 这给你在n/2 * log(n)哪个O(nlog(n))