Comment trouver le temps d'exécution d'une recherche binaire récursive? - algorithme, runtime, big-o, procédure

Pour chacune des procédures ci-dessous, prenons T (n) comme temps d'exécution. Trouver l'ordre de T (n) (c'est-à-dire, trouver f (n) tel que T (n) (f (n)).

Procedure BinarySearch(table T [a . . . b], int k):
if a > b then
return -1
end if
middle ← ⌊(a + b)/2⌋
if T [middle] = k then
return middle
end if
if k < T [middle] then
return BinarySearch(T [a . . .middle], k)
else
return BinarySearch(T [middle . . . b], k)
end if

Je sais comment trouver les temps d’exécution de fonctions simples, mais comme cela inclut les appels récursifs, j’ai des problèmes.

Réponses:

Ce lien (bas de la page) décrit un moyen très clair de résoudre la relation de récurrence de l’algorithme de recherche binaire.