Ja, man kan sige, at den bedste tidskompleksitet for den binære søgealgoritme er Theta(1), og at den værst tænkelige tidskompleksitet for den binære søgealgoritme er Theta(log n). For at forklare dette dykker vi ned i definitionerne af Big O, Big Omega og Big Theta, som alle er asymptotiske notationer til at beskrive algoritmernes løbetids- og rumkompleksitet.

Når man henviser til den bedste/værste løbetid for en algoritme, henviser man typisk til en enkelt funktion. Big O notation bruges til at beskrive algoritmer ved deres øvre grænse for løbetid, og Big Omega notation bruges til at beskrive algoritmer ved deres nedre grænse for løbetid.

Udtrykt på en enklere måde betyder Big O, at algoritmen ikke kan og vil ikke køre langsommere end den funktion, der er afgrænset inden for Big O. Big Omega betyder, at algoritmen ikke kan og vil ikke køre hurtigere end den funktion, der er afgrænset inden for Big Omega. For at kunne bruge Big Theta-notationen til at beskrive en algoritmes løbetidskompleksitet skal algoritmens løbetid omfatte den samme funktion for både Big O- og Big Omega-notationen.

I forbindelse med binær søgning beskrives det bedste tilfælde som værende det tilfælde, hvor det første element i søgealgoritmen er det element eller emne, som man søger efter. Det betyder, at uanset hvad der sker, behøver algoritmen kun at se på hverken mere eller mindre end ét enkelt element. Derfor kan denne situation beskrives at have en løbetid på O(1) og Omega(1). Da disse to funktioner er ens, er det korrekt at sige, at den binære søgealgoritmes bedste løbetid er Theta(1).

Det værste tilfælde af binær søgning beskrives som værende det tilfælde, hvor hvert element skal kigges på, og det sidste element, der kontrolleres, er det element, som søgningen søger, eller elementet findes simpelthen ikke i datastrukturen. Da Binary Search anvender begrebet Divide and Conquer til at undersøge hvert enkelt element, er det trivielt, at algoritmens løbetid i det værst tænkelige tilfælde må være begrænset af en form for (log n). Konkret kan vi sige, at den vil have en løbetid på både O(log n) og Theta(log n), fordi algoritmen ikke vil kunne køre hurtigere eller langsommere på grund af det fastsatte antal elementer, som den skal kigge på. I dette tilfælde er de to funktioner ens, så det er korrekt at sige, at den binære søgealgoritmes løbetid i værste tilfælde er Theta (1).