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 !
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 !