Let S[0 n 1] be an array that consists of n numbers. Given some value z, we wish to determine if there are two distinct numbers S[i] and S[j] so that S[i] + S[j] = z. 2

a. Heres a brute force way of solving this problem: For every pair of numbers in S, check if they sum up to z. If one such pair exists, output yes; otherwise, output no. What is the running time of this algorithm?

b. Suppose S is a sorted array. That is, the numbers are ordered from smallest to largest. Describe a faster algorithm that solves the problem. That is, its running time should be asymptotically smaller than the brute force algorithm described in part (a); its running time can be O(n log n) or O(n) time for example.