Da, se poate spune că complexitatea timpului de funcționare în cel mai bun caz pentru algoritmul de căutare binară este Theta(1) și că complexitatea timpului de funcționare în cel mai rău caz pentru algoritmul de căutare binară este Theta(log n). Pentru a explica acest lucru, vom aprofunda definițiile lui Big O, Big Omega și Big Theta, care sunt toate notații asimptotice pentru a descrie complexitatea timpului de execuție și a complexității spațiale a algoritmilor.

Când vă referiți la timpul de execuție în cel mai bun/cel mai rău caz al unui algoritm, vă referiți de obicei la o singură funcție. Notația Big O este utilizată pentru a descrie algoritmii prin limita superioară a timpului de execuție, iar notația Big Omega este utilizată pentru a descrie algoritmii prin limita inferioară a timpului de execuție.

Dispus într-un mod mai simplu, Big O înseamnă că algoritmul nu poate și nu va rula mai încet decât funcția delimitată în Big O. Big Omega înseamnă că algoritmul nu poate și nu va rula mai repede decât funcția delimitată în Big Omega. Pentru a utiliza notația Big Theta pentru a descrie complexitatea timpului de execuție a unui algoritm, timpul de execuție al algoritmului trebuie să includă aceeași funcție atât pentru notația Big O, cât și pentru notația Big Omega.

În cazul căutării binare, cel mai bun caz este descris ca fiind cel în care primul element din algoritmul de căutare este elementul sau elementul pe care îl căutați. Acest lucru înseamnă că, indiferent de ceea ce se întâmplă, algoritmul nu va trebui să se uite decât la nici mai mult, nici mai puțin de un singur element singular. Prin urmare, această situație poate fi descrisă ca având un timp de execuție de O(1) și Omega(1). Deoarece aceste două funcții sunt identice, este corect să spunem că timpul de execuție în cel mai bun caz al algoritmului de căutare binară este Theta(1).

Cazul cel mai defavorabil al căutării binare este descris ca fiind cazul în care fiecare element trebuie să fie analizat, iar ultimul element verificat este elementul pe care îl caută căutarea, sau elementul pur și simplu nu există în structura de date. Deoarece căutarea binară utilizează conceptul de împărțire și cucerire pentru a examina fiecare element, este banal ca timpul de execuție al algoritmului în cel mai rău caz să fie limitat de o anumită formă de (log n). Mai exact, putem spune că ar trebui să aibă un timp de funcționare atât de O(log n), cât și de Theta(log n), deoarece algoritmul nu ar putea funcționa nici mai repede, nici mai încet din cauza numărului de elemente pe care trebuie să le analizeze. În acest caz, cele două funcții sunt identice, deci este corect să spunem că timpul de execuție în cel mai rău caz al algoritmului de căutare binară este Theta (1).

.