NlogNの計算量

ソースコード

  long N=pow(10,18);
  printf("[N][logN][NlogN][N^2]\n");
  for(double i=10;i<=N;i*=10){
    printf("[%.0g][%.0g][%.0g][%.0g]\n",i,log2(i),i*log2(i),i*i);
  }

実行結果

[N][logN][NlogN][N^2]
[1e+01][3][3e+01][1e+02]
[1e+02][7][7e+02][1e+04]
[1e+03][1e+01][1e+04][1e+06]
[1e+04][1e+01][1e+05][1e+08]
[1e+05][2e+01][2e+06][1e+10]
[1e+06][2e+01][2e+07][1e+12]
[1e+07][2e+01][2e+08][1e+14]
[1e+08][3e+01][3e+09][1e+16]
[1e+09][3e+01][3e+10][1e+18]
[1e+10][3e+01][3e+11][1e+20]
[1e+11][4e+01][4e+12][1e+22]
[1e+12][4e+01][4e+13][1e+24]
[1e+13][4e+01][4e+14][1e+26]
[1e+14][5e+01][5e+15][1e+28]
[1e+15][5e+01][5e+16][1e+30]
[1e+16][5e+01][5e+17][1e+32]
[1e+17][6e+01][6e+18][1e+34]
[1e+18][6e+01][6e+19][1e+36]

考察

Nが$10^6$のときにNlogN(底は2)は2*$10^7$なので
1秒間に余裕を持って計算できるNlogNはNが$10^6$ぐらいまでですかね〜。