CLRS Exercises 2.3-7

Problem:

Describe a Θ(n lg n)-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.

Solution:

1. Merge sort the elements which will take O(n log n)
2. then have two pointers one from beginning and another from end
3. if sum of both the elements a[i]+a[j] < sum then i++
4. else if sum of both the elements a[i]+a[j] > sum then j--
5. else we found print those elements a[i] and a[j].
6. complexity is O(n) in worst case.
7. Alternatively, after merge sort, do binary search for tmp=Sum - a[i] in the array a[i+1 ... n]
8. here for binary search complexity is O(log n), so still total worst case complexity is O(n log n)

Complexity: O(n log n)
Code:

CLRS Exercises 2.3-5 Binary search

Problem:

Binary search is an algorithm that repeats this
procedure, halving the size of the remaining portion of the sequence each time. Write
pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running
time of binary search is Θ(lg n).

Solution:

1. If there are 2^i elements then the height of the tree will be i+1
2. At each level we will just do comparison [key with middle element] which is a constant time O(1)
3. So for any n, height of the tree will be log n + 1
4. Thus, worst case running complexity will be Θ(lg n).

Complexity: Θ(lg n).
Code: