Ce que la rencontre au milieu énumère vraiment

L'algorithme construit $2^{\lfloor n/2\rfloor }$ sommes à gauche et $2^{\lceil n/2\rceil }$ à droite, soit environ $2\cdot 2^{n/2}$ en tout — au lieu de $2^n$. Mesuré sur $n=20$ entiers :

Le rapport vaut $2^{n/2}/2$, soit $512$ pour $n=20$. Pour $n=40$, il vaut $2^{19}=524288$ : c'est le chiffre du cours, retrouvé.

Si $n$ est impair, n / 2 tronque et la première moitié a un élément de moins : $2^{(n-1)/2}$ contre $2^{(n+1)/2}$. Le déséquilibre coûte un facteur $\sqrt{2}$ sur le côté le plus gros, ce qui est sans importance. Ce qui importerait, ce serait de découper $1$ contre $n-1$ : on retomberait sur $2^{n-1}$, c'est-à-dire sur l'exhaustif. Le partage en deux moitiés égales n'est pas un détail d'écriture, c'est l'endroit où l'algorithme gagne : $2^a+2^{n-a}$ est minimal en $a=n/2$.

Où le temps passe réellement. Construire les sommes coûte $\Theta (2^{n/2})$ ; les trier coûte $\Theta (2^{n/2}\cdot n)$ ; les $2^{n/2}$ recherches dichotomiques coûtent $\Theta (2^{n/2}\cdot n)$ également. C'est donc le tri et les recherches qui dominent, d'où le $n$ du $O(2^{n/2}n)$ annoncé.

Et la mémoire. La rencontre au milieu stocke $2^{n/2}$ sommes ; à $n=40$, cela fait $10^6$ entiers, soit $8$ méga-octets — praticable. À $n=60$, ce serait $10^9$ entiers, soit $8$ gigaoctets. Cette méthode échange du temps contre de la mémoire, et c'est la mémoire qui devient la limite.