Wydajność części szukającej algorytmu Przy założeniu, że tablica T była już wyliczona, zamortyzowany koszt algorytmu Knutha-Morrisa-Pratta wynosi gdzie k jest długością tekstu S. Ponieważ większa część obliczeń wykonywana jest w pętli (dopóki), wystarczy, że oszacujemy maksymalną liczbę jej przebiegów. Rozpatrzmy najpierw najgorszy przypadek:
Gdy dla danych S=AAAAAABAC.... W=AAAAAA algorytm po znalezieniu częściowego dopasowania A6 (zaczynającego się na pozycji 0) natrafi na B (na pozycji 6), spróbuje odrzucić pierwsze A i rozpocznie z A5 (na pozycji 1), gdzie spróbuje dopasować A6. Wciąż jednak natrafia na B, będzie więc sukcesywnie cofał się krok po kroku aż do A1 (na pozycji 5). Dopiero potem, gdy i ta próba dopasowania zakończy się porażką, przejdzie do następnego znaku. Taka sytuacja wymaga operacji, gdy n jest długością wzorca. Gdy pomnożymy n przez k wyjdzie na to, że algorytm KMP nie jest szybszy od naiwnego algorytmu wyszukiwania wzorca. Zauważmy jednak, że algorytm, aby móc cofnąć się o jedno miejsce, musi wcześniej przeczytać przynajmniej jeden znak, zatem sytuacje takie jak ta mogą wystąpić jedynie w k/m przypadkach.