Diviser par deux ne rend pas logarithmique

(* somme des cases t.(g .. d-1), par dichotomie *)
let rec somme t g d =
  if d - g <= 1 then (if d - g = 1 then t.(g) else 0)
  else let m = (g + d) / 2 in somme t g m + somme t m d

La fonction est correcte, mais elle n'est pas logarithmique : elle est linéaire. Mesuré, en comptant les appels :

n :                  7    15    1000    100000    1000000
appels :            13    29    1999    199999    1999999
2n - 1 :            13    29    1999    199999    1999999

Pourquoi. La taille est bien divisée par deux, mais il y a deux appels par niveau : la récurrence est $T(n)=2T(n/2)+O(1)$, c'est-à-dire la deuxième forme du cours avec $a=2$. Le nombre d'appels double à chaque niveau et il y a ${\log }_{2}n$ niveaux, donc

$$1+2+4+\cdots +2^{{\log }_{2}n}=2n-1=\Theta (n).$$

L'arbre des appels a ${\log }_{2}n$ de hauteur et $2n-1$ de nœuds : ce sont bien les deux grandeurs que le cours distingue, et c'est la seconde qui donne le temps.

Ce qui est logarithmique, c'est $a=1$ : un seul appel par niveau. La dichotomie de recherche l'est, parce qu'elle jette une moitié ; la somme dichotomique ne l'est pas, parce qu'elle doit lire toutes les cases — et aucun algorithme ne peut sommer $n$ nombres sans les lire.

un seul appel par niveau (compte des bits de n) :
n = 1000 : 11 appels    n = 1000000 : 21 appels

La formulation juste du critère : ce n'est pas « je divise par deux » qui donne le logarithme, c'est « je divise par deux et j'abandonne une moitié ». La somme dichotomique reste néanmoins utile — elle a une profondeur de pile $\Theta (\log n)$ au lieu de $\Theta (n)$, et ses deux moitiés sont indépendantes, donc parallélisables (chapitre chap:concurrence).