Doerr, Doerr, Spöhel, and Thomas [1]} showed that the case \(k = n\)  is the last remaining case to be able to get tight asymptotic bounds for all \(k\) . For this reason we focus on this case only except for Section . We first run a randomized algorithm so that we can assume afterwards that the codeword is a permutation which makes the analysis cleaner. We believe it is possible to adapt the algorithm to deal with non-permutation codewords deterministically but we will not prove it here.
