Home » Other » Community Hangout » algorithmic question
algorithmic question Mon, 07 February 2011 16:05
 pyscho Messages: 134Registered: 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
 rleishman Messages: 3727Registered: 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: Book Project
Goto Forum:

Current Time: Tue Aug 22 00:35:55 CDT 2017

Total time taken to generate the page: 0.23196 seconds