Finally, when we introduce gappy state phrases of the type s i s j , the number of such phrases is O(m 2 ), since we may choose a start and end point independently.
the total complexity rises to O((Km + m 2 ) 2 Kn) = O(Km 4 n).