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
    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?2011-06-07
  • 0
    Sorry, I should have been clearer. I meant Integers from (1..n) and constant as in constant in the size of the output.2011-06-07
  • 0
    It depends on the condition. Can you be more specific?2011-06-07
  • 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