Prove that the following two problems have the same complexity by giving a linea

Question

Prove that the following two problems have the same complexity by giving a linear-time reductions between the two. 1. 3-SUM: given n integers x1, ..., x«, are there three distinct integers i, j, and k such that x+3-0 3-SUM-PLUS: given n integers x, and an integer b are there three distinct integers i.j, and k such that x+-b Give a linear-time reduction from 3-SUM-PLUS to 3-SUM. To demonstrate your reduction, give the 3-SUM instance that you would construct to solve the following 3-SUM-PLUS instance: b, xi, , & a.

Explanation / Answer

Consider an algorithm to find 3-SUM as following:

3-SUM(X[], n, sum):

1. size = n

2. for i 0 to size-2:

                        for j i+1 to size-1:

                                    for k j+1 to size:

                                                if A[i]+A[j]+A[k] == sum

                                                            print A[i],A[j],A[k]

3. return

This algorithm uses three loops to iterate over array A[] taking three at a time and if sum is "sum"" then print the triplet. Time complexity of this alogorithm is O(n^3).

Now consider algorithm for 3-SUM-PLUS which is going to call above code as below:

3-SUM-PLUS(X[], n, sum):

If sum == 0:

            3-SUM(X,n,0)

else

            3-SUM(X,n,sum)

           

This algorithm also take O(n^3) as call to 3-SUM takes constant time and 3-SUM itself takes O(n^3)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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