Tak, można powiedzieć, że złożoność czasowa najlepszego przypadku dla algorytmu wyszukiwania binarnego jest Theta(1) i że złożoność czasowa najgorszego przypadku dla algorytmu wyszukiwania binarnego jest Theta(log n). Aby to wyjaśnić, zagłębiamy się w definicje Big O, Big Omega i Big Theta, które są asymptotycznymi notacjami opisującymi czas działania i złożoność przestrzenną algorytmów.

Kiedy odnosimy się do najlepszego/najgorszego przypadku czasu działania algorytmu, zazwyczaj odnosimy się do pojedynczej funkcji. Notacja Big O jest używana do opisywania algorytmów przez ich górną granicę czasu działania, a notacja Big Omega jest używana do opisywania algorytmów przez ich dolną granicę czasu działania.

W przypadku wyszukiwania binarnego najlepszy przypadek jest opisany jako przypadek, w którym pierwszy element w algorytmie wyszukiwania jest elementem lub elementem, którego szukasz. Oznacza to, że bez względu na to, co się stanie, algorytm będzie musiał spojrzeć tylko na nie więcej i nie mniej niż jeden pojedynczy element. Dlatego można opisać tę sytuację, aby mieć czas działania O(1) i Omega(1). Ponieważ te dwie funkcje są takie same, można powiedzieć, że najlepszy czas działania algorytmu wyszukiwania binarnego to Theta(1).

Najgorszym przypadkiem wyszukiwania binarnego jest sytuacja, w której każdy element musi zostać sprawdzony, a ostatnim sprawdzanym elementem jest element, którego szuka wyszukiwanie, lub element ten po prostu nie istnieje w strukturze danych. Ponieważ wyszukiwanie binarne wykorzystuje koncepcję dziel i zwyciężaj (ang. Divide and Conquer) do sprawdzania każdego elementu, jest rzeczą trywialną, że czas działania algorytmu w najgorszym przypadku musi być ograniczony przez jakąś formę (log n). Konkretnie, możemy powiedzieć, że miałby on czas działania zarówno O(log n), jak i Theta(log n), ponieważ algorytm nie byłby w stanie działać ani szybciej, ani wolniej z powodu ustalonej liczby elementów, na które musi spojrzeć. W tym przypadku te dwie funkcje są takie same, więc poprawnie można powiedzieć, że najgorszy czas działania algorytmu wyszukiwania binarnego to Theta (1).