Ano, lze říci, že časová složitost binárního vyhledávacího algoritmu v nejlepším případě je Theta(1) a že časová složitost binárního vyhledávacího algoritmu v nejhorším případě je Theta(log n). Abychom to vysvětlili, ponoříme se do definic Big O, Big Omega a Big Theta, což jsou asymptotické zápisy pro popis časové a prostorové složitosti běhu algoritmů.

Když mluvíte o době běhu algoritmu v nejlepším/nejhorším případě, obvykle máte na mysli jednu funkci. Zápis Big O se používá k popisu algoritmů pomocí jejich horní hranice doby běhu a zápis Big Omega se používá k popisu algoritmů pomocí jejich dolní hranice doby běhu.

Jednodušeji řečeno, Big O znamená, že algoritmus nemůže a nebude běžet pomaleji než funkce ohraničená v rámci Big O. Big Omega znamená, že algoritmus nemůže a nebude běžet rychleji než funkce ohraničená v rámci Big Omega. Aby bylo možné použít notaci Big Theta k popisu časové složitosti běhu algoritmu, musí doba běhu algoritmu zahrnovat stejnou funkci pro obě notace Big O i Big Omega.

V případě binárního vyhledávání je nejlepší případ popsán tak, že prvním prvkem v algoritmu vyhledávání je hledaný prvek nebo položka. To znamená, že ať se stane cokoli, algoritmus bude muset prohledat pouze ne více a ne méně než jeden jediný prvek. Proto lze tuto situaci popsat tak, že má dobu běhu O(1) a Omega(1). Protože tyto dvě funkce jsou stejné, je správné říci, že nejlepší případ doby běhu algoritmu binárního vyhledávání je Theta(1).

Nejhorší případ binárního vyhledávání je popsán jako případ, kdy je třeba prohlédnout každý prvek a poslední kontrolovaný prvek je prvek, který vyhledávání hledá, nebo tento prvek v datové struktuře prostě neexistuje. Vzhledem k tomu, že binární vyhledávání využívá konceptu Rozděl a panuj k prohlédnutí každého prvku, je triviální, že doba běhu algoritmu v nejhorším případě musí být omezena nějakým tvarem (log n). Konkrétně můžeme říci, že by jeho doba běhu byla O(log n) i Theta(log n), protože algoritmus by nemohl běžet ani rychleji, ani pomaleji vzhledem k nastavenému počtu prvků, které musí prohlédnout. V tomto případě jsou obě funkce stejné, takže je správné říci, že doba běhu algoritmu binárního prohledávání je v nejhorším případě Theta(1).

.