そう、バイナリサーチ・アルゴリズムの最良の場合の実行時間複雑性はTheta(1)、最悪の場合の実行時間複雑性はTheta(log n)と言えるのです。 これを説明するために、アルゴリズムの実行時間と空間の複雑さを表す漸近的表記法であるビッグ O、ビッグ オメガ、ビッグ シータの定義を掘り下げます。

アルゴリズムのベスト/ワーストケース実行時間に言及する場合、通常は単一の関数に言及します。 アルゴリズムを上限の実行時間で記述する場合はBig O表記、下限の実行時間で記述する場合はBig Omega表記が使われる。

より簡単な方法で述べると、ビッグ O は、アルゴリズムがビッグ O 内で境界を定められた関数よりも遅く実行できない、また実行できないことを意味し、ビッグオメガは、アルゴリズムがビッグオメガ内で境界を定められた関数よりも速く実行できない、また実行できないことを意味します。 アルゴリズムの実行時間の複雑さを記述するためにビッグシータ表記を使用するためには、アルゴリズムの実行時間はビッグOとビッグオメガの両方の表記に対して同じ関数を含まなければならない。

Binary Searchの場合、ベストケースは、検索アルゴリズムの最初の要素が検索する要素またはアイテムである場合であると説明されている。 これは、何が起こっても、アルゴリズムは、それ以上でもそれ以下でもない特異な項目しか見なければならないことを意味します。 したがって、この状況は、実行時間がO(1)、Omega(1)であると表現できる。 これらの2つの関数が同じであるため、バイナリ検索アルゴリズムの最良の場合の実行時間はTheta(1)と言うのが正しい。

バイナリ検索の最悪の場合とは、すべての要素を調べる必要があり、最後にチェックした要素が検索対象の要素であるか、単にデータ構造内に要素が存在しない場合だと説明される。 バイナリサーチはDivide and Conquerの概念を利用して全ての要素を調べるので、最悪の場合のアルゴリズムの実行時間は何らかの形で(log n)で束縛されなければならないのは自明である。 具体的には、見なければならない要素の数が決まっているために、アルゴリズムがこれ以上速くも遅くもならないので、O(log n) と Theta(log n) の両方の実行時間を持つことになると言える。 この場合、2つの関数は同じなので、二項探索アルゴリズムの最悪の場合の実行時間はθ(1)と言うのが正しいです

。