Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
1) What are the things being multiplied in your multiplication table? 2) How can you expect to do anything in constant time when the output has (presumably) $n^2$ items? –  Robert Israel Jun 7 '11 at 3:03
    
Sorry, I should have been clearer. I meant Integers from (1..n) and constant as in constant in the size of the output. –  Ratzes Jun 7 '11 at 3:20
    
It depends on the condition. Can you be more specific? –  Yuval Filmus Jun 7 '11 at 3:24
    
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. –  Asaf Karagila Jun 7 '11 at 5:32

1 Answer 1

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
share|improve this answer
    
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.) –  ShreevatsaR Jun 7 '11 at 6:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.