As long as the weights are distributed randomly in the array, you can just perform the algorithm on a random subsection of the array. The subsection needs to h

As long as the weights are distributed randomly in the array, you can just perform the algorithm on a random subsection of the array. The subsection needs to have the same distribution of weights as the whole section. I think thats the only requirement you need. Ideally, you could pick smaller fraction of the array as N gets bigger, giving you sub O(N) scaling. In other words, if the array indexes that get picked using a slow algorithm are distributed randomnly, you might as well just pick a random subsection, as long as it is big enough to have the same distribution of W's as the whole array.