We are given an array that contains N numbers. We want to determine if there are

Question

We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1, 6, and K is 10, then the answer is yes (4 and 6).

A number may be used twice. Do the following: a. Give an O(N2) algorithm to solve this problem.

b. Give an O(N logN) algorithm to solve this problem. (Hint: Sort the items first. After that is done, you can solve the problem in linear time.)

c. Code both solutions and compare the running times of your algorithms.

Explanation / Answer

program by step by step:

We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1, 6, and K is 10, then the answer is yes (4 and 6)

a. found=false;

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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