Terry Reedy wrote: > If I understand correctly, you want to multiiply each of m numbers by each > of n numbers, giving m*n products. That is O(m*n) work. Inserting (and > extracting) each of these is a constant size m priority cue takes, I > believe, O(log(m)) work, for a total of m*n*log(m). That is faster than > O(m*n*log(m*n)) for sorting m*n random numbers.
According to this page: http://maven.smith.edu/~orourke/TOPP/P41.html You are very close. The only thing is whether the logarithmic factor can be removed. But there's more: </quote> If the input consists of n integers between - M and M, an algorithm of Seidel based on fast Fourier transforms runs in O(n + M log M) time [Eri99a]. The $ \Omega$(n2) lower bounds require exponentially large integers. <quote> So maybe there is something at least for this specific case. I hope I'm not irritating someone by posting my thought processes here, since posting things sometimes seems to be the only way to find the links. I wonder if it's the selective attention that makes them turn up after posting or whether your talk about big O's has put me on the right track. Thanks anyway. The problem is still open in general, but some hacks are possible, as Paul Rubin said. A. -- http://mail.python.org/mailman/listinfo/python-list
