Oui, on peut dire que la complexité temporelle d’exécution dans le meilleur des cas de l’algorithme de recherche binaire est Thêta(1) et que la complexité temporelle d’exécution dans le pire des cas de l’algorithme de recherche binaire est Thêta(log n). Pour expliquer cela, nous nous plongeons dans les définitions de Big O, Big Omega et Big Theta qui sont toutes des notations asymptotiques pour décrire les complexités de temps d’exécution et d’espace des algorithmes.

Lorsque vous faites référence au meilleur/pireux temps d’exécution d’un algorithme, vous faites généralement référence à une seule fonction. La notation Big O est utilisée pour décrire les algorithmes par leur temps d’exécution limite supérieure et la notation Big Omega est utilisée pour décrire les algorithmes par leur temps d’exécution limite inférieure.

Dit d’une manière plus simple, Big O signifie que l’algorithme ne peut pas et ne s’exécutera pas plus lentement que la fonction bornée dans Big O. Big Omega signifie que l’algorithme ne peut pas et ne s’exécutera pas plus rapidement que la fonction bornée dans Big Omega. Afin d’utiliser la notation Big Theta pour décrire la complexité du temps d’exécution d’un algorithme, le temps d’exécution de l’algorithme doit inclure la même fonction pour les deux notations Big O et Big Omega.

Dans le cas de la recherche binaire, le meilleur cas est décrit comme étant le cas où le premier élément de l’algorithme de recherche est l’élément ou l’item que vous recherchez. Cela signifie que, quoi qu’il arrive, l’algorithme ne devra examiner ni plus ni moins d’un élément singulier. Par conséquent, on peut décrire cette situation comme ayant un temps d’exécution de O(1) et Omega(1). Puisque ces deux fonctions sont les mêmes, il est correct de dire que le temps d’exécution du meilleur cas de l’algorithme de recherche binaire est Thêta(1).

Le pire cas de la recherche binaire est décrit comme étant le cas où chaque élément doit être regardé et où le dernier élément vérifié est l’élément que la recherche cherche, ou l’élément n’existe tout simplement pas dans la structure de données. Étant donné que la recherche binaire utilise le concept de division et de conquête pour examiner chaque élément, il est trivial que le temps d’exécution de l’algorithme, dans le pire des cas, soit limité par une forme de (log n). Plus précisément, nous pouvons dire que le temps d’exécution serait à la fois O(log n) et Thêta(log n), car l’algorithme ne pourrait pas fonctionner plus vite ou plus lentement en raison du nombre d’éléments qu’il doit examiner. Dans ce cas, les deux fonctions sont les mêmes, il est donc correct de dire que le temps d’exécution le plus défavorable de l’algorithme de recherche binaire est Thêta (1).