Exercise 2.3-7

[IgorSuharev]

After sorting of S, a search of two a, b in S such that a + b = x can be improved.

FIND-SUM(S, x) // Indexes in S are 1, 2, ..., n
S = SORT(S)
i = 1
j = n
while i < j
    sum = S[i] + S[j]
    if sum == x
        return TRUE
    if sum < x
        i = i + 1
    else
        j = j - 1
return FALSE

Using this way, the time complexity of the search is Θ(n) instead of Θ(n lgn). (But, it's obviously that time complexity of entire algorithm stays same.)

[funny1dog]

Yes, you are right, but the final time complexity stays the same.