Algorithm's Running Time Optimization

Question

I'm trying to find a way to optimize my algorithm such that the running time is O(n²) (Big O Notation).

The input is an array with n elements, of only positive and negative integers. We can assume that the array is already sorted.

I have to determine: for each r (element of the array), whether r = s + t, where s and t are also elements of the array, and can be the same (s == t), or also zero.

I tried to reduce the number of elements I have to check by checking if the current number is positive or negative, but the running time is still too long. The problem is that I'm using 3 while loops which already means a running time of O(n³) for the worst case.

Here is my code:

public static void Checker(int[] array) {
    List<Integer> testlist = new ArrayList<Integer>();
    int i = 0;
    while (i < array.length) {
        int current = array[i];
        if (attached(current, array)) {
            testlist.add(current);
        }
        i++;
    }
}

public static boolean attached(int current, int[] array) {
    boolean result = false;
    int i = 0;
    while (i < array.length && !result) {
        int number1 = array[i];
        int j = 0;
        while (j < array.length && !result) {
            int number2 = array[j];
            if (number1 + number2 == current) {
                result = true;
            }
            j++;
        }
        i++;
    }
    return result;
}

Firstly, add all elements from array to HashSet, then iterate over s and t and check if s + t is presented in your set. — michael-tkach, Apr 28 '16 at 13:53
Please don't use code formatting as highlighting, it makes things very hard to read. — Esoteric Screen Name, Apr 28 '16 at 14:09

score 2 · Answer 1 · answered Apr 28 '16 at 13:51

2

calculate all the possible sums of s+t and put the results in a set => O(n²)
iterate over each r and check if there is a sum that matches r => O(n) since set.contains runs in constant time.

answered Apr 28 '16 at 13:51

assylias

321,522
82
660
783

score 2 · Accepted Answer · edited May 23 '17 at 12:31

You can start sorting the array O(nlogn) (if not), then for each element in the array you can check if there are two elements that the sum is equals to the number in O(n²).

The code is in C#:

public static bool Solve(int[] arr)
{
    Array.Sort(arr);    //If not already sorted

    foreach (var num in arr)
        if (!FindTwoThatSumN(arr, num))
            return false;

    return true;
}

public static bool FindTwoThatSumN(int[] arr, int num)
{
    int min = 0;
    int max = arr.Length - 1;

    while (true)
    {
        if (min == max) break;

        int sum = arr[min] + arr[max];

        if (sum < num) min++;
        if (sum > num) max--;
        if (sum == num) return true;
    }

    return false;
}

The idea to check if there are two numbers in an array (must be sorted) that sum a specific value is start from the minimum (min = 0) and the maximum (max = arr.Length), then in each iteration:

If the sum is lower than the number, increase min index.
If the sum is greater than the number, decrease max index.
If the sum is equals to the number, then you find a solution.
If min index reach max then there are no solution.

You can refer to this question/answers for more details and proof.

Time complexity for overall solution is O(n²):

Sort the array: O(nlogn).
Iterate over the sorted array: O(n).
Find two numbers that sum the value: O(n).

So, is O(n²) due the nested calls to FindTwoThatSumN.

If you want you can pass the index instead of the number to FindTwoThatSumN method to avoid with an additional check use the number itself as part of the solution.

Algorithm's Running Time Optimization

2 Answers2