## 2 Materials and Methods
### Deterministic Algorithms
#### 2.2.3 An \(O(n\sqrt{k\log k})\) Time Algorithm for \(K\) Mismatches
The algorithm in [11] chooses \(2k\) instances of distinct characters to perform marking. Therefore, for every position of the text, at most one mark is created. If the number ofmarks is \(M\), then the cost of the marking phase is \(O(n+M)\). The number of remaining positions after filtering is no more than \(M/k\), and thus, the algorithm takes \(O(n+M)\) time. Our algorithm puts in the knapsack 2k instances, of not necessarily different characters, such that the number of marks \(B\) is minimized!Therefore, \(B\leq M\), and the total runtime is \(O(n+B)\). Case 2: \(|\Sigma|<2\sqrt{k}\). The algorithm in [11] performs one convolution per character to count the total number of matches for every alignment, for a run time of \(\Omega(|\Sigma|n\log m)\). In the worst case, knapsack \(k\) mismatches cannot fill the knapsack at a cost \(B<|\Sigma|n\log m\), so it defaults to the same run time. However, in the best case, the knapsack can be filled at a cost \(B\) as low as \(O(n)\) depending on the frequency of the characters in the pattern and the text. In this case, the runtime will be \(O(n)\). Case 3: \(2\sqrt{k}\leq|\Sigma|\leq 2k\). A symbol that appears in the pattern at least \(2\sqrt{k}\) times is called frequent. Case 3.1: There are at least \(\sqrt{k}\) frequent symbols. The algorithm in [11] chooses \(2\sqrt{k}\) instances of \(\sqrt{k}\) frequent symbols to do marking and filtering at a cost \(M\leq 2n\sqrt{k}\). Since knapsack \(k\) mismatches will minimize the marking time \(B\), we have \(B\leq M\), so the run time is the same as for [11] only in the worst case. Case 3.2: There are \(A<\sqrt{k}\) frequent symbols. The algorithm in [11] first performs one convolution for each frequent character for a run time of \(O(An\log m)\). Two cases remain:  
Case 3.2.1: All of the instances of the non-frequent symbols number less than \(2k\) positions. The algorithm in [11] replaces all instances of frequent characters with wild cards and applies a \(O(n\sqrt{g}\log m)\) algorithm to count mismatches, where \(g\) is the number of non-wild card positions. Since \(g<2k\), the run time for this stage is \(O(n\sqrt{k}\log m)\), and the total run time is \(O(An\log m+n\sqrt{k}\log m)\). Knapsack \(k\) mismatches can always include in the knapsack all of the instances of non-frequent symbols, since their total cost is no more than \(O(n\sqrt{k})\), and in the worst case, do convolutions for the remaining characters. The total run time is \(O(An\log m+n\sqrt{k})\). Of course, depending on the frequency of the characters in the pattern and text, knapsack \(k\) mismatch may not have to do any convolutions. Case 3.2.2: All of the instances of the non-frequent symbols number at least \(2k\) positions. The algorithm in [11] chooses \(2k\) instances of infrequent characters to do marking. Since each character has a frequency less than \(2\sqrt{k}\), the time for marking is \(M<2n\sqrt{k}\), and there are no more than \(M/k\) positions left after filtering. Knapsack \(k\) mismatches chooses characters in order to minimize the time \(B\) for marking, so again \(B\leq M\). \(\qed\)