The binary search needs at most \(\lceil \lg_2(n+1)\rceil\) iterations, and in each iteration the slowest operation is the comparison of the suffix \(M=T[S[m]..]\) with the pattern \(P\), which in the worst case compares \(|P|\) characters in \(O(|P|)\) time. \(x > c_l\) In this case, we know that \(P\) is larger than \(L\) in the \(c_l+1\)‘st character, and since \(x>c_l\), \(L\) and \(M\) are equal in their \(c_l+1\)‘st character, so also \(P\) is larger than \(M\) in its \(l+1\)‘st character and \(P>M\), so we branch right. The main difference between the faster search and the LCP based search is that the faster search starts comparing characters between \(P\) and \(M\) at the \(\min(c_l, c_r)+1\)‘st character, while the LCP version starts at the \(\max(c_l, c_r)+1\)‘st character.