Kyllä, voidaan sanoa, että binäärihakualgoritmin parhaan tapauksen ajallinen monimutkaisuus on Theta(1) ja että binäärihakualgoritmin huonoimman tapauksen ajallinen monimutkaisuus on Theta(log n). Selittääksemme tämän syvennymme Big O:n, Big Omegan ja Big Thetan määritelmiin, jotka kaikki ovat asymptoottisia merkintöjä kuvaamaan algoritmien juoksuaika- ja tilakompleksisuuksia.

Viitattaessa algoritmin parhaaseen/huonoimpaan tapaukseen perustuvaan juoksuaikaan viitataan tyypillisesti yhteen funktioon. Big O -merkintätapaa käytetään kuvaamaan algoritmeja niiden ylemmän käyttöajan avulla ja Big Omega -merkintätapaa kuvaamaan algoritmeja niiden alemman käyttöajan avulla.

Yksinkertaisemmin ilmaistuna Big O tarkoittaa, että algoritmi ei voi eikä tule toimimaan hitaammin kuin Big O:n sisällä rajattu funktio. Big Omega tarkoittaa, että algoritmi ei voi eikä tule toimimaan nopeammin kuin Big O:n sisällä rajattu funktio. Jotta voidaan käyttää Big Theta -merkintää kuvaamaan algoritmin juoksuaikakompleksisuutta, algoritmin juoksuajan on sisällettävä sama funktio sekä Big O- että Big Omega -merkinnöissä.

Binäärisen haun tapauksessa paras tapaus kuvataan tapaukseksi, jossa hakualgoritmin ensimmäinen alkio on etsimäsi alkio tai kohde. Tämä tarkoittaa, että tapahtuipa mitä tahansa, algoritmi joutuu tarkastelemaan vain korkeintaan yhtä ja korkeintaan yhtä yksittäistä elementtiä. Siksi tämän tilanteen voidaan kuvata olevan ajoaikaltaan O(1) ja Omega(1). Koska nämä kaksi funktiota ovat samat, on oikein sanoa, että binäärihakualgoritmin parhaan tapauksen juoksuaika on Theta(1).

Binäärihaun huonoimmaksi tapaukseksi kuvataan tilanne, jossa jokaista elementtiä on tarkasteltava ja viimeinen tarkastettu elementti on se elementti, jota haku etsii, tai elementtiä ei yksinkertaisesti ole olemassa tietorakenteessa. Koska binäärihaku käyttää divide and conquer -konseptia jokaisen elementin tarkasteluun, on triviaalia, että algoritmin suoritusajan on pahimmassa tapauksessa oltava rajoitettu jollakin (log n). Tarkemmin sanottuna voidaan sanoa, että algoritmin suoritusaika olisi sekä O(log n) että Theta(log n), koska algoritmi ei voisi toimia yhtään nopeammin tai hitaammin niiden elementtien lukumäärän vuoksi, joita sen on tarkasteltava. Tässä tapauksessa nämä kaksi funktiota ovat samat, joten on oikein sanoa, että binäärihakualgoritmin pahimman tapauksen ajoaika on Theta(1).