2. In this exercise, you will develop a quadratic-time algorithm for the 3-sum p

Question

2. In this exercise, you will develop a quadratic-time algorithm for the 3-sum problem. When we ask you to design an algorithm, give a crisp and concise English description of your algorithm—don't write Java code.

A. Given an integer x and a sorted array a[] of N distinct integers, design a linear-time algorithm to find if there exists two distinct indices i and j such that (a[i] + a[j] == x). (20 Points)

Hint: start by checking whether a[0] + a[N-1] is smaller than, greater than, or equal to x.

B. Given an array a[] of N distinct integers, design a quadratic-time algorithm to find if there exists three distinct indices i, j, and k such that (a[i] + a[j] + a[k] == 0). (20 Points)

Hint: Use the result from (a). You can assume the array is sorted since sorting the array can be done in quadratic (and even linearithmic) time.

Explanation / Answer

2
A. The alogorithm is as follows:

   We will start traversing from start and the last a[0] and a[n-1].We will add them and
   see if sum = x. If sum > x, the last index will be decremeted as the array is
   sorted and we need a smaller number. Now if sun < x , then the first index will
   move forwars as we need a bigger number. This is a linear aprroach as we are
   either moving from last or moving from front based on the value of the sum.If both
   the index meet and we don't get the number this means there are no two numbers
   whose sum is x

B. Now we have three indices or three numbers a[i] + a[j] + a[k] = 0 .From this
   we can have a[i] + a[j] = -a[k]. Now this can be found with linear complexity.
   Now we can change the value for k = 1..n. We are checking k for every value of
   n. So this means the complexity will be n*n . So it is O(n^2) which is quadratic.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

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