Ja, je kunt zeggen dat de best-case looptijdcomplexiteit voor het binaire zoekalgoritme Theta(1) is en dat de worst-case looptijdcomplexiteit voor het binaire zoekalgoritme Theta(log n) is. Om dit uit te leggen, duiken we in de definities van Big O, Big Omega, en Big Theta, die allemaal asymptotische notaties zijn om de looptijd en ruimte-complexiteit van algoritmen te beschrijven.

Wanneer je het hebt over de best/worst-case looptijd van een algoritme, heb je het meestal over een enkele functie. De Big O-notatie wordt gebruikt om algoritmen te beschrijven met hun bovenlimiet-looptijd en de Big Omega-notatie wordt gebruikt om algoritmen te beschrijven met hun onderlimiet-looptijd.

Eenvoudiger gezegd, Big O betekent dat het algoritme niet langzamer kan en zal lopen dan de functie begrensd binnen Big O. Big Omega betekent dat het algoritme niet sneller kan en zal lopen dan de functie begrensd binnen Big Omega. Om de Big Theta notatie te gebruiken om de looptijd van een algoritme te beschrijven, moet de looptijd van het algoritme dezelfde functie bevatten voor zowel de Big O als de Big Omega notatie.

In het geval van binair zoeken, wordt het beste geval beschreven als het geval waarin het eerste element in het zoekalgoritme het element of item is waarnaar je zoekt. Dit betekent dat, wat er ook gebeurt, het algoritme slechts naar niet meer en niet minder dan één enkel element hoeft te kijken. Daarom kan deze situatie worden beschreven met een looptijd van O(1) en Omega(1). Aangezien deze twee functies gelijk zijn, is het juist om te zeggen dat de best-case looptijd van het binaire zoekalgoritme Theta(1) is.

Het slechtste geval van binair zoeken wordt beschreven als het geval waarin naar elk element moet worden gekeken en het laatst gecontroleerde element het element is waarnaar wordt gezocht, of het element simpelweg niet bestaat binnen de datastructuur. Aangezien binair zoeken gebruik maakt van het concept Verdeel en heers om elk element te bekijken, is het triviaal dat de looptijd van het algoritme in het slechtste geval begrensd moet zijn door een vorm van (log n). In het bijzonder kunnen we zeggen dat het een looptijd heeft van zowel O(log n) als Theta(log n) omdat het algoritme niet sneller of langzamer kan lopen vanwege het aantal elementen dat het moet bekijken. In dit geval zijn de twee functies gelijk, dus is het juist om te zeggen dat de slechtst denkbare looptijd van het binaire zoekalgoritme Theta (1) is.