Question-3 (15 pts: two_sum is a Python function that takes in a list of integer

Question

Question-3 (15 pts: two_sum is a Python function that takes in a list of integers (elements) and an integer number (num), and returns True if there exists two values in elements that add up to num, otherwise, function returns False. def two_sum (elements: List[int], num: int) for i in range (len (elements)): for j in range (i + 1): if elements[i] + elementsil um return True return False Study above function and answer below questions: A- B- What is time complexity of two surm Is it possible to improve on above algorithm performance (in terms of its asymptotic cost)? If yes, describe your algorithm, be detailed as much as possible.

Explanation / Answer

Hey,

Below are the answers to your questions

A)

Complexity of two_sum() function is O(n^2) where n are the number of elements in List elements. It is due to the fact that i vary from 0 to n and j further varies as 0,1,2,3,4.....n. Giving a total bound of O(n^2).

B)

It can be done with efficiency of O(n) by hashing.

def two_sum(elements: List[int], num: int)

      bool s[10000] = {0};

       for i in range(len(elements)):

             temp = sum - elements[i];

             if (temp >= 0 && s[temp] == 1)

                    return True;

            s[elements[i]] = 1;

return False

Kindly revert for any queries

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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