Sí, se puede decir que la complejidad del tiempo de ejecución en el mejor caso para el algoritmo de búsqueda binaria es Theta(1) y que la complejidad del tiempo de ejecución en el peor caso para el algoritmo de búsqueda binaria es Theta(log n). Para explicar esto, profundizamos en las definiciones de Big O, Big Omega y Big Theta, que son notaciones asintóticas para describir el tiempo de ejecución y las complejidades espaciales de los algoritmos.

Cuando se habla del tiempo de ejecución en el mejor/peor de los casos de un algoritmo, normalmente se hace referencia a una única función. La notación Big O se utiliza para describir algoritmos por su tiempo de ejecución de límite superior y la notación Big Omega se utiliza para describir algoritmos por su tiempo de ejecución de límite inferior.

Expresado de una manera más simple, Big O significa que el algoritmo no puede y no se ejecutará más lento que la función limitada dentro de Big O. Big Omega significa que el algoritmo no puede y no se ejecutará más rápido que la función limitada dentro de Big Omega. Para utilizar la notación Big Theta para describir la complejidad del tiempo de ejecución de un algoritmo, el tiempo de ejecución del algoritmo debe incluir la misma función tanto para la notación Big O como para la notación Big Omega.

En el caso de la búsqueda binaria, el mejor caso se describe como el caso en el que el primer elemento del algoritmo de búsqueda es el elemento o ítem que se está buscando. Esto significa que, pase lo que pase, el algoritmo sólo tendrá que mirar ni más ni menos que un elemento singular. Por lo tanto, se puede describir esta situación para tener un tiempo de ejecución de O(1) y Omega(1). Como estas dos funciones son iguales, es correcto decir que el tiempo de ejecución del algoritmo de búsqueda binaria en el mejor de los casos es Theta(1).

El peor caso de la Búsqueda Binaria se describe como el caso en el que hay que mirar cada elemento y el último elemento comprobado es el elemento que la búsqueda está buscando, o el elemento simplemente no existe dentro de la estructura de datos. Dado que la búsqueda binaria utiliza el concepto de dividir y conquistar para buscar cada elemento, es trivial que el tiempo de ejecución del algoritmo en su peor caso debe estar limitado por alguna forma de (log n). En concreto, podemos decir que tendría un tiempo de ejecución tanto de O(log n) como de Theta(log n) porque el algoritmo no podría ejecutarse ni más rápido ni más lento debido al número conjunto de elementos que debe mirar. En este caso, las dos funciones son iguales, por lo que es correcto decir que el tiempo de ejecución en el peor caso del algoritmo de búsqueda binaria es Theta (1).