Home » Other » Community Hangout » algorithmic question
algorithmic question [message #493411] Mon, 07 February 2011 16:05 Go to next message
pyscho
Messages: 134
Registered: December 2009
Senior Member
If given a set of numbers and a number n, find if there are 2 numbers in the set that add up to n. (O(n lgn) time) is optimal, n^2 is the simple answer

any ideas?
Re: algorithmic question [message #493471 is a reply to message #493411] Tue, 08 February 2011 05:05 Go to previous message
rleishman
Messages: 3683
Registered: October 2005
Location: Melbourne, Australia
Senior Member
CREATE TABLE NUMS (NUM NUMBER);


{populate NUMS}

SELECT A.NUM, B.NUM
FROM   NUMS A
JOIN   NUMS B
ON     B.NUM = :N - A.NUM;


Unfortunately, this does not meet your requirement because it is O(n) (assuming it performed a hash join), which is better than O(n log n). To achieve O(n log n) you would have to artificially slow it down by performing an Indexed Nested Loop, thus:

CREATE INDEX NUMS_IX ON NUMS(NUM);

SELECT /*+ ORDERED USE_NL(B) INDEX(B) */ A.NUM, B.NUM
FROM   NUMS A
JOIN   NUMS B
ON     B.NUM = :N - A.NUM;


Ross Leishman
Previous Topic: Closed, not a bug
Next Topic: People from down under
Goto Forum:
  


Current Time: Tue Jul 22 04:35:07 CDT 2014

Total time taken to generate the page: 0.09174 seconds