I do not want a solution if my own answer is incorrect because i really want to solve this on my own. What i do want is either a yes this is correct or a no this is not correct, followed by tips or suggestions that may lead to an answer without spoiling it all.
The question:
Describe a theta(nlgn)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x. (Intro to Algorithms, 2.3-7)
The attempt:
First the problem doesnt state whether or not the set is sorted. I assumed it was not, and sorted it using merge sort as it is theta(nlgn) under the worst case.
Then i said okay, the only way this will still be theta(nlgn) is if i recursively split the problem into two. My approach was to start at index i=0 of our array, see what value k would i need for x=i+k and then used binary search to split the problem in half until i either found k or not. If i did not find a k such that x=i+k, then i would continue the same process for index i=2 to n-1. This would result in theta(nlgn).
The total time complexity from both sorting the array and finding k would add up to theta(nlgn) + theta(nlgn) = theta(2nlg2n) = theta(nlgn) if you remove constants.
