Could someone help me optimize this code for time complexity? What is the best way to do this that doesn't include nested for loops?
Take an array of integers and return a list of sums of every combination of 2 numbers. So, for this array
[1,2,3]
, spit out"3,4,5 (1+2, 1+3, 2+3)."
Here is a possible solution using \$O(n^2)\$ time complexity:
static List<int> returnSums(int[] integers)
{
List<int> sums = new List<int>();
for (int x = 0; x < integers.Length; x++)
{
for (int y = x + 1; y < integers.Length; y++)
{
sums.Add(integers[x] + integers[y]);
}
}
return sums;
}
Is there a way to write this with \$O(n)\$?
n*(n-1)/2
numbers, which can't be done inO(n)
time (because it'sO(n^2)
in space). However, list additions areO(log n)
amortised, so you are currently doing this inO(n^2 log(n))
: pre-allocating the list gives youO(n^2)
(just need to provide an argument tonew List<int>(/*length*/)
\$\endgroup\$ – VisualMelon Oct 3 '17 at 19:34n*(n-1)/2
wheren
isintegers.Length
(i.e. the output count), I just couldn't be bothered to type it before ;) (Reading again, my original comment was woefully ambiguous: sorry about that) \$\endgroup\$ – VisualMelon Oct 3 '17 at 20:43y
at0
instead ofx+1
) \$\endgroup\$ – VisualMelon Oct 3 '17 at 20:52