# A Deeper Look into TwoSum

## 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 + arr = 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 `N2 + 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++`
01N - 1
12N - 2
23N - 3
N-2N-11
N-1N0

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 `j`s (`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 `N2/2`times since it’s inside both for loops for a total of `4N2/2 = 2N2`.

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 N2 + 2N + 2N2 + 2`
`= 3N2 + 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 `N2`) and say `twoSumSlow ∈ O(N2)` where `N` is the length of the input array.