I might be wrong but that looks like O(n^2) in the worst case, namely when the input is some permutation of (a+k, a+2k,...,a+nk).