Trois seuils, et ce qu'une machine mille fois plus rapide y change

On cherche le plus grand $n$ tel que la quantité reste sous le budget. Les valeurs ci-dessous ont été calculées, pas estimées.

Les bornes exactes : $2^{29}=536870912$ et $2^{30}=1073741824$ ; $12!=479001600$ et $13!=6227020800$ ; $3^{18}=387420489$ et $3^{19}=1162261467$.

Ce que ce calcul enseigne, et c'est le point de tout le chapitre. Multiplier la puissance de la machine par mille fait gagner $10$ sur les sous-ensembles, $7$ sur les mots ternaires, et $2$ sur les permutations. Autrement dit : mille fois plus de calcul ajoute deux objets à un problème de permutations.

C'est un fait général et il se lit sur la formule : si le budget est multiplié par $B$, le seuil de $2^n$ augmente de ${\log }_{2}B$ et celui de $3^n$ de ${\log }_{3}B$ — donc logarithmiquement. Pour $n!$, la croissance est encore plus rapide que toute exponentielle, et le gain est plus faible encore.

Un algorithme exponentiel ne devient jamais praticable par l'attente. C'est un raisonnement, et non une mesure, qui le fait tomber : c'est l'objet des chapitres chap:diviser, chap:gloutons et chap:dynamique.