nlogn対nの平方根、平方根の方が遅いですか？

Question

私はオンラインコースでこのクイズをやっていました。

機能nlogn +√N+ 5は
Aに属するように設定してもよい。nlogn
B：
C√N：

n√nクイズの正解であるが、前記nの平方根は遅くないのですか？私はアルゴリズムの時間の複雑さを見いだすのが初めてで、説明を使うことができます。答えが間違っている場合は、私に知らせてください。

Answer 1

nを非常に大きな数値と見なす必要があります。任意の場合、n>2、n>√nおよびlogn>1。従って、nlogn>√n。

Answer 2

正しいHierachyはこれです：

超線形[ n log n]>リニア[n]>サブ多項式[n^(1/a)]

場合a: a >= 1.

したがってn log n = O(n) = O(sqrt(n))

N「は極めて多数である必要はありませんビッグオーは無限の限界を扱っていますが、特に、あなたはあなたのことを設定することができますn0は `b +として、bは対数の底である。この場合は10.

あなた自身で調べるとn=11でテストしてください。