Instrumenter les deux jointures — naïve et indexée — pour compter…

def fusion_naive_compte(t1, t2, cle):
    comp = 0
    res = []
    for a in t1:
        for b in t2:
            comp = comp + 1
            if a[cle] == b[cle]:
                c = dict(a)
                c.update(b)
                res.append(c)
    return res, comp

def fusion_indexee_compte(t1, t2, cle):
    op = 0
    index = {}
    for b in t2:
        index[b[cle]] = b
        op = op + 1
    res = []
    for a in t1:
        op = op + 1
        if a[cle] in index:
            c = dict(a)
            c.update(index[a[cle]])
            res.append(c)
    return res, op

Sur deux tables de même taille $n$ :

Les lois sont confirmées, et mieux que confirmées. Le compteur naïf vaut exactement $n^2$ sur les quatre tailles, et l'indexé exactement $2n$ — les deux assertions cn == n <em> n et ci == 2 </em> n passent. Le rapport $4,0$ à chaque doublement est la signature du quadratique ; le rapport $2,0$, celle du linéaire.

Ce que la mesure ajoute à la formule. Rien, quand la formule est juste — et c'est justement ce qu'on voulait vérifier. Une mesure qui donnerait $3,1$ au lieu de $4,0$ dirait qu'on s'est trompé quelque part : soit dans le raisonnement, soit dans le compteur. Annoncer une complexité sans la mesurer, c'est se priver de ce contrôle.

Une limite honnête. On compte des opérations, pas des secondes. Le temps réel dépend de la machine, du cache, de l'interpréteur ; il suit la même loi, mais avec du bruit. C'est pourquoi on compte plutôt qu'on ne chronomètre.