algorithm - c > 0 のとき Log(n) = O(n)? O(log n) ではない理由がわからない

Question

私の宿題では、質問は n^.99999*log(n) の漸近的な複雑さを決定するよう求めています。O( n log n) に近いと思いましたが、答えの鍵は、c > 0 の場合、log n = O(n) であることを示唆しています。それがなぜなのかよくわかりません。誰かが説明を提供できますか？

Answer 1

lg n = O( n ^k ) (実際、それは o( n ^k ) です。ヒントは実際にそう言っているのでしょうか?) 1 だけでなく、任意の定数kについても真実です。ここで、 k =0.00001 を考えます。次にn ^0.99999 lg n = O( n ^0.99999 n ^0.00001 ) = O( n ) です。さらに小さいkを選択できるため、この境界は厳密ではないことに注意してください。そのため、 n ^0.99999 lg nは O( n ^0.99999 lg nであると言っても問題ありません。)、ちょうどn lg nが O( n lg n ) であると言うように。