big-o - 関数に Big O、Big Theta、Big Omega を与える

Question

次のような関数に Big O、Big Theta、または Big Omega を与えるにはどうすればよいですか

T(n) = n + 10*log n

誰かが私にそのようなことの複雑さを得る方法を教えてもらえますか?

Answer 1

下位の項と定数をすべて削除すると、次のようになります。

Θ(T(n)) = Θ(n + 10*log(n)) = Θ(n)

これはタイトな境界 ( Θ) であるため、上限と下限もO(n)およびとして推論しΩ(n)ます。