Help me make this algorithm faster---!

[TangDN]

Hi guys. I don't see how I can possibly make this algorithm faster to the point of O(n lg n)...

I have a number X and an array Y. I have to find if there are two numbers in array Y that sum up to X.
All I can think up is to:
Go through every element in Y and add it up to Y+i ; for i->n // where n is the number of elements in Y
if Y+Yi = X return true.

This looks to me to run in O(n^2) time. But I get bonus points to make it run faster. Any suggestions? Quicksort runs in O( n lg n ) so I think QuickSort and then check to see if numbers add up, would take too long. Or am I wrong about how time analysis of algorithms work? Thanks !

 

[Adrian Tung]

Here's a shot in the dark, I hope someone else can improve it or suggest a better one:

Quicksort, but discard all numbers that are larger than X-1. The go through the sorted array, each time continuing the next loop once you hit the point where the sum of the numbers are larger than X.

Oh, and this is assuming that there are no negative numbers. If there are, I think it won't cost much to try and detect the lowest number, then discard all numbers larger than X-1-(lowest number) during the quicksort.


Hope that helps,
atwl

 

[DaveSimmons]

Two words: binary search.
That's probably too much of a hint, and saying more would certainly be doing your homework for you.

 

[kt]

Like DaveSimmons says, construct a binary tree with X as the pivot. I am not sure if the construct of the binary tree is being counted into the O notation though. Been a while since I took a class.. any class for that matter.

 

[DaveSimmons]

<< Like DaveSimmons says, construct a binary tree with X as the pivot. I am not sure if the construct of the binary tree is being counted into the O notation though. Been a while since I took a class.. any class for that matter. >>

Hmm, I'm too lazy to look it up, but doesn't tree construction take o(n log n) iteself? then creating a tree per X (= n trees) would take O(n^2 log n) which is too slow. My approach was tree-free, using binary search of something else. Note that O(n log n) + O(n log n) is still O(n log n) even though (n * O(n log n)) is not.

 

[m0ti]

sort the array (heap sort is best ... guaranteed WORST time of O(n log n)).

then go over the array, doing a binary search for each number. (for example, if the first number is -1 do a search for X+1. if a number is 7 do a search for X-7).

Actually, you only have to go over the array till you get to X/2. Also, remember that you should only find the number at an index you haven't visited yet! (If you're at X/2, you'll find X/2 in a binary search. just make sure that it isn't the same one as the one you started at. This can be done easily, if you do the binary search on the array taking the starting index as the next one than the place you're currently checking!)

Time for sort: O(n log n)
Time for search n * O(log n) = O (n log n)

grand total of... O(n log n).

 

[kt]

<<

<< Like DaveSimmons says, construct a binary tree with X as the pivot. I am not sure if the construct of the binary tree is being counted into the O notation though. Been a while since I took a class.. any class for that matter. >>

Hmm, I'm too lazy to look it up, but doesn't tree construction take o(n log n) iteself? then creating a tree per X (= n trees) would take O(n^2 log n) which is too slow. My approach was tree-free, using binary search of something else. Note that O(n log n) + O(n log n) is still O(n log n) even though (n * O(n log n)) is not. >>


Maybe I've misunderstood his question, but I am under the impression that there's only one X value. So, you'll only need to construct one binary search tree. While you are constructing the BST, you have already eliminated all the impossible values (all values in array Y that are greater than X). So, you only have to search thru the left hand side of the tree. Worst case scenerio would be all values in array Y is less than X.. then all hell breaks loose.

 

[DaveSimmons]

<< Maybe I've misunderstood his question, but I am under the impression that there's only one X value. So, you'll only need to construct one binary search tree. >>

d'oh! You're right, I shouldn't post in my sleep . My approach was the sort - then - search process m0ti described, but yours will also work since it's really the same approach: (sort the numbers somehow) (do n binary searches for pairs) which works as long as the sort is (n log n) and each search is (log n).

 

[TangDN]

Sup guys. The binary search suggestion hit the problem right on the head... here's how it went down.

First sort the array of N integers using merge sort ---------- O( n lg n )
Then binary search it for a number that equaled x-N for i = 0 to length of N
if ever an index to such a number was returned from the binary search, return true
else if all indexs were searched and nothing found return false

Runtime:
Merge Sort --- O(n lg n)
Binary search --- O( lg n )
number of times searched worse case--- O(n)
thus, O( n lg n )

Since merge sort dominates --- O(n lg n) for algorithm!

Thanks for all the help everyone!