0

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)

stalris
  • 15
  • 1
  • 6

1 Answers1

2

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/

AKSingh
  • 1,535
  • 1
  • 8
  • 17
  • 2
    I have updated my answer and added a link to more optimal solutions to the given problem. – AKSingh Feb 12 '21 at 16:38
  • Any chance you eloborate how nCk = O(n^k) when k is fixed? I saw this [thread](https://math.stackexchange.com/questions/1265519/approximation-of-combination-n-choose-k-theta-left-nk-right) the Math Stackexchange but I got stuck when they factored n^k out of (n)(n-1)(n-2)...(n-k+1) – stalris Feb 12 '21 at 16:40
  • I have again updated my answer to explain how it results in an n^2 complexity. I am sorry I can not elaborate on how nCk = O(n^k) in this answer as it requires a separate answer of its own – AKSingh Feb 12 '21 at 17:14