[解決済み] Low boundとTight boundの違いは何ですか？

質問

これを参考に 回答 シータ（tight bound）とは何ですか？

オメガは下限値で、アルゴリズムにかかる時間の最小値であることはよく理解できます。Big-Oは上界で、アルゴリズムにかかる時間の最大値を意味することが分かっています。 しかし、私はシータに関しては全くわかりません。

どのように解決するのですか？

ビッグ・オー は上限値であり、一方 オメガ は下限です。 シータ はビッグ・オーとオメガの両方を必要とするので、そのために タイトバインド (上界と下界の両方でなければならない）。

例えば、あるアルゴリズムが Omega(n log n) は少なくとも n log n 時間であり、上限はない。アルゴリズムにかかる Theta(n log n) を要するので、はるかに優遇されています。 少なくとも n log n (オメガ n log n)と 以下 n log n (Big O n log n)である。