Igen, azt mondhatjuk, hogy a bináris keresési algoritmus legjobb esetre vonatkozó futási időbonyolultsága Theta(1), a legrosszabb esetre vonatkozó futási időbonyolultsága pedig Theta(log n). Ennek magyarázatához elmélyedünk a Big O, Big Omega és Big Theta definícióiban, amelyek mind aszimptotikus jelölések az algoritmusok futási idő- és térbonyolultságának leírására.

Az algoritmus legjobb/legrosszabb esetű futási idejére való hivatkozáskor általában egyetlen függvényre utalunk. A Big O jelölést az algoritmusok felső korlátos futási idejükkel, a Big Omega jelölést pedig az algoritmusok alsó korlátos futási idejével való leírására használják.

Egyszerűbben fogalmazva, a Big O azt jelenti, hogy az algoritmus nem tud és nem is fog lassabban futni, mint a Big O-n belül behatárolt függvény, a Big Omega pedig azt, hogy az algoritmus nem tud és nem is fog gyorsabban futni, mint a Big O-n belül behatárolt függvény. Ahhoz, hogy a Big Theta jelölést használjuk egy algoritmus futási időbonyolultságának leírására, az algoritmus futási idejének ugyanazt a függvényt kell tartalmaznia mind a Big O, mind a Big Omega jelölés esetén.

A bináris keresés esetében a legjobb esetnek azt az esetet írjuk le, amikor a keresési algoritmus első eleme az az elem vagy elem, amelyet keresünk. Ez azt jelenti, hogy bármi történjék is, az algoritmusnak csak legfeljebb egy és legfeljebb egy egyedi elemet kell megvizsgálnia. Ezért ez a helyzet leírható úgy, hogy futási ideje O(1) és Omega(1). Mivel ez a két függvény megegyezik, helyesen mondhatjuk, hogy a bináris kereső algoritmus legjobb esetben a futási ideje Theta(1).

A bináris keresés legrosszabb eseteként azt az esetet írjuk le, amikor minden elemet meg kell nézni, és az utolsó ellenőrzött elem az, amit a keresés keres, vagy az elem egyszerűen nem létezik az adatstruktúrában. Mivel a Bináris keresés az Oszd meg és uralkodj koncepciót használja az összes elem átnézésére, triviális, hogy az algoritmus futási ideje a legrosszabb esetben valamilyen (log n)-el kell, hogy legyen korlátozva. Konkrétan azt mondhatjuk, hogy a futási ideje O(log n) és Theta(log n) lenne, mert az algoritmus nem tudna sem gyorsabban, sem lassabban futni a megnézendő elemek meghatározott száma miatt. Ebben az esetben a két függvény megegyezik, ezért helyes azt mondani, hogy a bináris kereső algoritmus legrosszabb esetben Theta(1) futási ideje.