Search code examples
algorithmsortingmergesortheapsort

Check if in ArrayList of size N, there are two numbers which their sum is N

I have homework to do. I have to implement an algorithm, which has to check, if, into an ArrayList, of size N, there are at least two numbers, which added, their sum is N. The complexity of the algorithm has to be Theta(n log n). I already know that I can use the Merge.Sort, or, the Heap-Sort, then I have to subtract the size of the array list, with every element, of the array list. The question is: Subtracting sequentially the complexity, will still be Theta(n log n)?!? If not, how can I keep it that way?

Solution

  • Sort the array with MergeSort for O(n log n) then for each record r_i in the array perform a lookup for record N - r_i using binary search which is O(log n)

    You will have O(n log n) for mergeSort + O(n log n) for n binary search lookups --> O(n log n)