1
\$\begingroup\$

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)\$?

\$\endgroup\$
  • 3
    \$\begingroup\$ There is not, because you have to output n*(n-1)/2 numbers, which can't be done in O(n) time (because it's O(n^2) in space). However, list additions are O(log n) amortised, so you are currently doing this in O(n^2 log(n)): pre-allocating the list gives you O(n^2) (just need to provide an argument to new List<int>(/*length*/) \$\endgroup\$ – VisualMelon Oct 3 '17 at 19:34
  • 1
    \$\begingroup\$ Not quite: the length needs to be n*(n-1)/2 where n is integers.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:43
  • 3
    \$\begingroup\$ Yes, your output size is a function of the Triangle Numbers: hopefully the pictures on Wikipedia combined with a bit of imagination will make it obvious why ;) (for an extra hint: start by thinking about what would happen if you start y at 0 instead of x+1) \$\endgroup\$ – VisualMelon Oct 3 '17 at 20:52
  • 1
    \$\begingroup\$ Ohhhh I get it... because, my output isn't the size of the array being passed, it's the number of values being returned. That was easy to see with a debugger. Good thing I wasn't being required to pick that out in a whiteboard interview. Now your entire comment about having to output n*(n-1)/2 TOTALLY makes sense. \$\endgroup\$ – Christine Oct 3 '17 at 21:00
  • 1
    \$\begingroup\$ @VisualMelon Your analysis should be posted as an answer. \$\endgroup\$ – 200_success Oct 4 '17 at 0:23
2
\$\begingroup\$

The code is fine, and asymptotically optimal. There is a potential speedup by preallocating the output list to the correct size, but it's at best a factor of 2. VisualMelon's comment is unnecessarily pessimistic: List<T>.Add has an amortised cost of \$O(1)\$, although to show that it's necessary to rely on implementation details which are not in the API documentation.

There are some small improvements which could be made. The spec asks for "a list" rather than "a List", so I see no reason not to follow the principle of coding to the interface. I would prefer to return IList<int> or IReadOnlyList<int>.

The other thing is names. The return in returnSums doesn't tell me anything useful. How about pairwiseSums? And instead of x and y I would use i and j, which are de facto standard variable names for array indices for reasons going back to FORTRAN's type system.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That is terribly embarrassing, my Algorithmics lecturer would be most disappointed... I'm going to have to review this stuff. Good commentary as usual. (Would one not quote the cost as O(1), amortisation referring to the cost of an operation in context, rather than the total cost?) \$\endgroup\$ – VisualMelon Oct 4 '17 at 8:39
  • \$\begingroup\$ Oops! I accidentally claimed an even more pessimistic bound. It is indeed O(1). \$\endgroup\$ – Peter Taylor Oct 4 '17 at 8:45
0
\$\begingroup\$

I don't think you can do this without nested loops.

This

x < integers.Length

Can be

x < integers.Length - 1 

But is will not save much

Return IEnumerable if you can

You can spare an array lookup

This is how I would write this

static IEnumerable<int> returnSums(int[] integers)
{
    for (int i = 0; i < integers.Length - 1; i++)
    {
        int outer = integers[i];
        for (int j = i + 1; j < integers.Length; j++)
        {
            yield return outer + integers[j];
        }
    }
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.