# A Deeper Look into TwoSum

## Table of contents

## Problem

Recall that an algorithm for TwoSum takes in an array of integers and a target number. It’ll return the indicies of distinct integers within the array that sum up to the target. If it can’t find two such integers, it’ll return -1, -1.

For example:

```
int[] example = new int[] {1, 9, 3, 0, 8, 5};
// Should output {1, 5} (arr[1] + arr[5] = 9 + 5 = 14
System.out.println(Arrays.toString(twoSumSlow(example, 14)));
// Should output {-1, -1}
System.out.println(Arrays.toString(twoSumSlow(example, 42)));
```

## Code

Here’s the code for the “slow” version of TwoSum:

```
public static int[] twoSumSlow(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
if (arr[i] + arr[j] == target) {
return new int[] {i, j};
}
}
}
return new int[] {-1, -1};
}
```

## Full Runtime Analysis

In order to find the runtime of `twoSumSlow`

, let’s count every step of the code as a function of `N`

, where `N`

is the size of the array.

First off, we have the outer for loop:

```
for (int i = 0; i < arr.length; i++) {
```

This line takes one step for `int i = 0;`

, `N`

steps for each check against the length of the array, and `N`

steps for the increment, for a total of `2N + 1`

. **Note that when we looked at this for loop, we added up all the checks that we we would make while we iterate through the length of the array.**

```
for (int j = i+1; j < arr.length; j++) {
```

The inner for loop is a bit more challenging. We have two steps for `int j = i+1;`

(addition, then assignment), We do roughly `N/2`

checks on average every time we’re checking the length of the array, and another `N/2`

for the increment. Total, this comes out to `N+2`

per iteration. **Since we execute the inner for loop N times, the overall cost is N**

^{2}+ 2N.

Now how did we get `N/2`

on average? Since `j`

depends on `i`

, we have the following relationship while iterating through the array:

`i` | `j` | # of `j++` |
---|---|---|

0 | 1 | N - 1 |

1 | 2 | N - 2 |

2 | 3 | N - 3 |

… | … | … |

N-2 | N-1 | 1 |

N-1 | N | 0 |

Observe that there’s an inverse relationship between `i`

/`j`

, and the number of times `j++`

gets called in each inner for loop (as `i`

and `j`

go up, the number of times `j++`

gets called during that iteration goes down.)

**Since we have N different js (1, 2, .., N-1, N), the number of increments on average is approximately N/2 (actually N/2 - 1/2, but let’s fudge it for simplicity.)**

Now all that’s left is the `if`

check and the `return`

:

```
if (arr[i] + arr[j] == target) {
return new int[] {i, j};
}
```

The `if`

will take 4 steps each time (2 array lookups, one addition, one equality check). We’ll run the `if`

roughly `N`

times since it’s inside both for loops for a total of ^{2}/2`4N`

.^{2}/2 = 2N^{2}

Since we only `return`

once, we’ll only need to add two steps for creating a new array and returning it. Likewise, we don’t need to add any more steps to count the `return new int[] {-1, -1}`

since we will only either return inside the `if`

, or at the end.

All in all, here’s our total number of steps in terms of `N`

, the length of the array:

`2N + 1 N`

^{2} + 2N + 2N^{2} + 2`= `

**3N ^{2} + 4N + 3**

Finally, since we’re able to use Big-O notation, we can ignore the smaller terms (`4N + 3`

) and the multiplcative constants (the 3 in front of the `N`

) and say ^{2}`twoSumSlow ∈ O(N`

where ^{2})`N`

is the length of the input array.