\par The justification is very similar to the argument that the number of iterations in \method {KMPMatch} is $O(n)$. \par Define $k = i - j$ for the sake of analysis. One of the following conditions occurs at each iteration of the loop: \begin {itemize} \item If $P[i]=P[j]$, then $i$ increases by $1$, and $k$ does not change, since $j$ also increases by~$1$. \item If $P[i] \neq P[j]$ and $j>0$, then $i$ does not change and $k$ increases by at least $1$, since in this case $k$ changes from $i-j$ to $i-f(j-1)$, which is an addition of $j-f(j-1)$, which is positive because $f(j-1) < j$. \item If $P[i] \neq P[j]$ and $j=0$, then $i$ increases by $1$ and $k$ increases by $1$, since $j$ does not change. \end {itemize} \par As a result, the number of iterations is at most $2m$. Therefore, \method {KMPFailureFunction} runs in $O(m)$ time.