2
$\begingroup$

this is my first post and I hope its succinct and relevant enough to post here.

I'm working on finding the largest number in a multiplication table (n by n) that satisfies a certain property. In finding the largest number, I realize that you can just sort the elements in the table, or get a bit smarter and do something like a saddle back search, checking each element for your property in order.

However, I was wondering if there was a way to sort the elements in a multiplication table in constant time, as with a pen and a pencil it seems that there is some sort of pattern.

Thanks!

  • 0
    This is linear time, constant time is when it is independent of the input size (asymptotically, that is). Please be sure to correct your question, if this is indeed what you meant.2011-06-07

1 Answers 1

2

By "constant", I guess you mean "linear".

Let $A$ be an array of integers indexed by the integers 1 to $n^2$, initialized to 0.

for i from 1 to n    for j from 1 to n      A[i*j]:= A[i*j] + 1  for i from 1 to n^2   for j from 1 to A[i]      output i 
  • 0
    Haha. Of course this is linear in $n^2$, the number of entries in the table. Perhaps the OP meant linear in the number m of *distinct* numbers in the table, in which case this is about O(m log m) (right? haven't thought carefully), still about as good as one can do. (Well, one could sieve out the primes in $[n+1, n^2]$, which would be slightly better—O(m log log m) arithmetic operations—but hardly worth it for the range of n where O(n) is acceptable.)2011-06-07