Let S[0 · · · n 1] be an array that consists of n numbers. Given some value z, w

Question

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. Here’s 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.

Explanation / Answer

Ans. a. Since we have to check this for every pair using brute forece and total pairs = n C 2 (n choose 2) which is of O(n^2),
Therefore, running time = O(n^2).

Ans. b. Take 2 pointers. One at the first index and other at the last index.
If sum < z, increase the first pointer.
Else if sum > z, decrease the second pointer.
Else, output "Yes"
Do this until both the indices meet at a point.
Time complexity: O(n).

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.