In: Computer Science
Suppose you are given an n-element array containing distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm?
In the above question, since the integers are in an increasing order, we can deduce that they are sorted already.
Now we need to find the complexity of finding the two integers whose sum can be k, if such pair exists.
The best approach would be that we start comparing the two elements in loop. starting from first and last element.
Lets refer to below code to see how to do this:
Eg: Our array is { 2,3 ,5, 7,9 }, k=16
Now I take the first element-2 and last element 9
2+9=11 which is less than 16.
So I move one element ahead from the left side which is the second element ->3
3+9=12 which is less than 16.
So I move one element ahead from left again.->5
9+5=14 which is than 16.
Again I move 1 ahead-> 7
7+9=16. Now we find a pair which has such pair of element.
Now what will be the complexity?
At worst case we will have to traverse the whole array till the end.
If there are n elements, then complexity will be O(n).