CODEWITHSUNDEEP
algorithm
stalris
stalris

Reputation: 15

Two Sum and its Time Complexity

I was going over both solutions to Two Sum on leetcode and I noticed that the n^2 solution is to basically test all combinations of two numbers and see if they sum to Target.

I understand the naive solution iterates over each element of the array( or more precisely n-1 times because we can't compare the last element to itself) to grab the first addend and then another loop to grab all of the following elements. This second loop needs to iterate n-1-i times where i is the index of the first addend. I can see that (n-1)(n-1-i) is O(n^2).

The problem comes when I googled "algorithm for finding combinations" and it lead to this thread where the accepted answer talks about Gray Codes which goes way above my head.

Now I'm unsure whether my assumption was correct, the naive solution is a version of a Gray Code, or something else.

If Two Sum is a combinations problem then it's Time Complexity would be O(n!/ ((n-k)! k!)) or O(nCk) but I don't see how that reduces to O(n^2)

Upvotes: 0

Views: 4630

Answers (1)

Anuj
Anuj

Reputation: 1665

I read the Two Sum question and it states that:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

It is a combinations problem. However, on closer inspection you will find that here the value of k is fixed.

You need to find two numbers from a list of given numbers that add up to a particular target.

Any two numbers from n numbers can be selected in nC2 ways.

nC2 = n!/((n-2)! * 2!)

= n*(n-1)*(n-2)!/((n-2)!*2)

= n*(n-1)/2

= (n^2 - n)/2

Ignoring n and the constant 2 as it will hardly matter when n tends to infinity. The expressions finally results in a complexity of O(n^2).

Hence, a naïve solution of Two Sum has a complexity of O(n^2). Check this article for more information on your question.

https://www.geeksforgeeks.org/given-an-array-a-and-a-number-x-check-for-pair-in-a-with-sum-as-x/

Upvotes: 2

Related Questions