Sim, você pode dizer que a melhor complexidade de tempo de execução para o algoritmo de pesquisa binária é Theta(1) e que a pior complexidade de tempo de execução para o algoritmo de pesquisa binária é Theta(log n). Para explicar isto, nós nos aprofundamos nas definições de Big O, Big Omega, e Big Theta que são todas notações assimptóticas para descrever o tempo de execução e complexidades de espaço dos algoritmos.

Quando você se refere ao melhor/pior caso de tempo de execução de um algoritmo, você está tipicamente se referindo a uma única função. A notação Big O é usada para descrever algoritmos pelo seu tempo de execução do limite superior e a notação Big Omega é usada para descrever algoritmos pelo seu tempo de execução do limite inferior.

Estabelecido de uma forma mais simples, Big O significa que o algoritmo não pode e não irá correr mais lentamente do que a função limitada dentro do Big O. Big Omega significa que o algoritmo não pode e não irá correr mais rapidamente do que a função limitada dentro do Big Omega. Para usar a notação Big Theta para descrever a complexidade do tempo de execução de um algoritmo, o tempo de execução do algoritmo deve incluir a mesma função para ambas as notações Big O e Big Omega.

No caso da Pesquisa Binária, o melhor caso é descrito para ser o caso quando o primeiro elemento no algoritmo de pesquisa é o elemento ou item que você está procurando. Isto significa que não importa o que aconteça, o algoritmo só terá que olhar para não mais e não menos do que um item singular. Portanto, esta situação pode ser descrita para ter um tempo de execução de O(1) e Omega(1). Como essas duas funções são as mesmas, é correto dizer que o melhor tempo de execução do algoritmo de busca binária é Theta(1).

O pior caso de busca binária é descrito para ser o caso quando cada elemento precisa ser visto e o último elemento verificado é o elemento que a busca está procurando, ou o elemento simplesmente não existe dentro da estrutura de dados. Como a Busca Binária utiliza o conceito de Divide and Conquer para olhar cada elemento, é trivial que o tempo de execução do algoritmo no seu pior caso deva ser limitado por alguma forma de (log n). Especificamente, podemos dizer que ele teria um tempo de execução de O(log n) e Theta(log n) porque o algoritmo não seria capaz de rodar mais rápido ou mais lento devido ao número definido de elementos que ele deve olhar. Neste caso, as duas funções são as mesmas, por isso é correcto dizer que o tempo de execução do algoritmo de pesquisa binária é Theta (1).