Le pire cas de la recherche de facteur, exactement

On choisit un texte constitué d'une répétition de lettres a : $s={\text{a}}^n$, et un motif constitué de lettres a terminées par un b : $m={\text{a}}^{p-1}\text{b}$. Pour chaque position de départ $i\in \{0,\dots ,n-p\}$, la boucle interne compare les $p-1$ premiers caractères du motif (qui coïncident avec les a du texte) puis échoue lors de la comparaison du dernier caractère. Chaque position de départ requiert exactement $p$ comparaisons. Le nombre total de comparaisons effectuées est : $$C(n)=(n-p+1)\times p$$ Pour $p=n/2$, ce coût vaut approximativement $n^2/4=\Theta (n^2)$. Le pire cas théorique quadratique est bien atteint.