Ja, man kan säga att den binära sökalgoritmens tidskomplexitet i bästa fall är Theta(1) och att den binära sökalgoritmens tidskomplexitet i värsta fall är Theta(log n). För att förklara detta fördjupar vi oss i definitionerna av Big O, Big Omega och Big Theta som alla är asymptotiska notationer för att beskriva algoritmers löptids- och utrymmeskomplexitet.

När man hänvisar till den bästa/värsta löptiden för en algoritm hänvisar man vanligtvis till en enda funktion. Big O-notation används för att beskriva algoritmer genom deras övre gräns för löptid och Big Omega-notation används för att beskriva algoritmer genom deras nedre gräns för löptid.

Enklare uttryckt betyder Big O att algoritmen inte kan och inte kommer att köras långsammare än den funktion som avgränsas inom Big O. Big Omega betyder att algoritmen inte kan och inte kommer att köras snabbare än den funktion som avgränsas inom Big Omega. För att kunna använda Big Theta-notationen för att beskriva en algoritms löptidskomplexitet måste algoritmens löptid inkludera samma funktion för både Big O- och Big Omega-notationerna.

I fallet med binär sökning beskrivs det bästa fallet som fallet när det första elementet i sökalgoritmen är det element eller föremål som du söker efter. Detta innebär att oavsett vad som händer kommer algoritmen bara att behöva titta på varken mer eller mindre än ett singulärt element. Därför kan denna situation beskrivas som att den har en körtid på O(1) och Omega(1). Eftersom dessa två funktioner är desamma är det korrekt att säga att den binära sökalgoritmens bästa fall av löptid är Theta(1).

Det sämsta fallet av binär sökning beskrivs vara fallet när varje element måste tittas på och det sista elementet som kontrolleras är det element som sökningen letar efter, eller så finns elementet helt enkelt inte i datastrukturen. Eftersom Binary Search använder begreppet Divide and Conquer för att undersöka varje element är det trivialt att algoritmens körtid i värsta fall måste begränsas av någon form av (log n). Vi kan säga att den skulle ha en körtid på både O(log n) och Theta(log n) eftersom algoritmen inte skulle kunna köras snabbare eller långsammare på grund av det fastställda antalet element som den måste titta på. I det här fallet är de två funktionerna samma, så det är korrekt att säga att den binära sökalgoritmens värsta gångtid är Theta (1).