Big O表記を使用するタイミングと大きなTheta表記を使用するタイミング

Question

Big Oは上限であり、Big Thetaは、例えば関数f（n）= O（g（n） ）またはBig Thetaの場合も同様です。 しかし、特定のアルゴリズムがBig Oの代わりにBig theta表記法を使用して表現されることをどのようにして知ることができますか？

たとえば、選択ソートの時間複雑さは、N^2のBig OではなくN^2のBig Thetaとして与えられます。なぜですか？

Answer 1

これはどちらが良いかという質問ではなく、むしろ勉強したいことです。 最悪の場合のシナリオを調べる場合は、上限の表記法を使用できます。境界がより緻密になるほどよいが、厳密な境界を計算することが困難な場合もあることに注意してください。 一般に、ビッグオーバやビッグテーダについて話すときには、同じことを意味します。選択ソートでは、ビッグオーモ式を使用することもできます。