In all of the following sub-questions, give an algorithm in recursive form and s

Question

In all of the following sub-questions, give an algorithm in recursive form and show its running time using the Master Theorem or just by solving the recurrence in the simpler cases.

C) Describe a (n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest sum. D) Describe a (n lg n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest difference. E) Describe a (n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactlyX.

Explanation / Answer

c)Let us take the example of merge sort and we can explain all the 3 cases as given in the question.

The merge function runs in Theta(n) (n) time when merging n elements.

We start by thinking about the three parts of divide-and-conquer and how to account for their running times.

We assume that we're sorting a total of n elements in the entire array.

D)&E) The solution is as follows.

SUM-X(S, x)

1 MERGE SORT(S)

2 i 1

3 j n

4 while i < j

5 do if S[i] + S[j] < x

6 then i i + 1

7 else if S[i] + S[j] > x

8 then j j – 1

9 else return S[i], S[j]

10 if i = j

11 then return nil

Proof of correctness:

Initially i = 1 and j = n.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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