Le programme précise que « l'aspect dynamique des tableaux de Python…

import time

for n in (100000, 200000, 400000, 800000):
    t0 = time.perf_counter()
    t = []
    for i in range(n):
        t.append(i)
    print(n, "-> %.4f s" % (time.perf_counter() - t0))
# 100000 -> 0.0038 s   200000 -> 0.0076 s
# 400000 -> 0.0160 s   800000 -> 0.0314 s

Première observation : doubler $n$ double le temps. Le coût est donc proportionnel à $n$, ce qui signifie que chaque append coûte en moyenne une constante. C'est loin d'être évident : un tableau occupe des cases contiguës, et quand il n'y a plus de place, il faut tout recopier ailleurs. Python s'en sort en réservant à chaque fois beaucoup plus que nécessaire, si bien que les recopies deviennent de plus en plus rares. On dit que le coût est constant amorti.

Seconde mesure, et la surprise.

t0 = time.perf_counter()
t = []
for i in range(20000):
    t = t + [i]              # au lieu de t.append(i)
print("%.4f s" % (time.perf_counter() - t0))     # 0.4827 s

$20000$ ajouts par t = t + [i] prennent près d'une demi-seconde, quand $800000$ append en prenaient trois centièmes. La différence n'est pas d'un facteur deux, elle est d'un facteur plusieurs centaines.

L'explication. t + [i] construit un nouveau tableau et y recopie les $k$ éléments existants. Le total est $1+2+\cdots +n=\frac{n(n+1)}{2}$ recopies : le coût est quadratique. t.append(i) écrit une seule case dans le tableau existant.

Deux écritures presque identiques à l'œil, deux coûts de nature différente. C'est la raison de fond pour laquelle le programme demande de raisonner à taille fixe : tant qu'on n'a pas les outils du chapitre 7 pour compter les opérations, le caractère dynamique d'un tableau donne une fausse impression de gratuité.