Significant Running time difference between two algorithms solving same task

Question

In the process of learning algorithms, I have written code to compare 2 algorithms performance in terms of running time. The task of these algorithms is to find all the pairs of numbers in an array that add up to a specific number.

First approach - Brute force. 2 for loops to find the pairs of numbers that add up to the given number. Basically time complexity is O(n*n).

Second approach - Efficient First sort the array, then have start and end as index to the beginning and end of array, and depending on the sum of these elements in the positions, move left or right to find pairs of numbers.

My question is - I am printing the running time of each algorithm approach. But it seems like the running time of the Brute force approach is faster than the Efficient one. Why is this happening?

See the code here -

public class MainRunner {

final private static int numberRange = 100000;

public static void generateRandomNumbers(int[] array, int[] dupArray) {
    System.out.println("Generated Array: ");
    Random random = new Random();
    for (int i = 0; i < array.length; i++) {
        int generatedRandomInt = random.nextInt(array.length) + 1;
        array[i] = dupArray[i] = generatedRandomInt;
    }
}

public static void main(String[] args) {
    int[] array = new int[numberRange];
    int[] dupArray = new int[numberRange];

    generateRandomNumbers(array, dupArray);

    Random random = new Random();
    int sumToFind = random.nextInt(numberRange) + 1;
    System.out.println("\n\nSum to find: " + sumToFind);

    // Starting Sort and Find Pairs
    final long startTimeSortAndFindPairs = System.currentTimeMillis();
    new SortAndFindPairs().sortAndFindPairsOfNumbers(sumToFind, array);
    final long durationSortAndFind = System.currentTimeMillis() - startTimeSortAndFindPairs;

    // Starting Find Pairs
    final long startTimeFindPairs = System.currentTimeMillis();
    new FindPairs().findPairs(sumToFind, dupArray);
    final long durationFindPairs = System.currentTimeMillis() - startTimeFindPairs;

    System.out.println("Sort and Find Pairs: " + durationSortAndFind);
    System.out.println("Find Pairs: " + durationFindPairs);
    }
}

SortAndFindPairs.java

public class SortAndFindPairs {

public void sortAndFindPairsOfNumbers(int argNumberToFind, int[] array) {
    Arrays.sort(array);

    System.out.println("\n\nResults of Sort and Find Pairs: \n");
    int startIndex = 0;
    int endIndex = array.length - 1;

    while (startIndex < endIndex) {
        int sum = array[startIndex] + array[endIndex];
        if (argNumberToFind == sum) {
            //System.out.println(array[startIndex] + ", " + array[endIndex]);
            startIndex++;
            endIndex--;
        } else if (argNumberToFind > sum) {
            startIndex++;
        } else {
            endIndex--;
        }
    }
}

And the FindPairs.java

public class FindPairs {

public void findPairs(int argNumberToFind, int[] array) {
    System.out.println("\nResults of Find Pairs: \n");
    int randomInt1 = 0;
    int randomInt2 = 0;
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = i + 1; j < array.length; j++) {
            int sum = array[i] + array[j];
            if (argNumberToFind == sum) {
                //System.out.println(array[i] + ", " + array[j]);
                //randomInt1++;
                //randomInt2--;

            }
        }
    }
}}

Only on adding the two variables randomInt1 and randomInt2 in the FindPairs.java, the running time difference is seen. Or else, the running time of FindPairs.java is much less than SortAndFindPairs.java. So why does adding just 2 variable operations increase time by so much? According to conventions, simple operations should consume negligible time. Am I missing out something here?

Results for numberRange = 1000000

Results of Find Pairs:

Sort and Find Pairs: 641 Find Pairs: 57

Answer 1

I think the problem is your compiler optimization playing tricks to you. I tried different permutations of your code, and noticed that the double for loop in FindPairs is doing almost nothing. So the compiler may be stripping some of the code.

I got this numbers with the exact copy of your code:

Sort and Find Pairs: 43 Find Pairs: 13

Consistently (I ran it several times to double check) Sort and find was slower, everytime.

But then I changed the inner loop for to do nothing:

for (int j = i + 1; j < array.length; j++) {
        //int sum = array[i] + array[j];
        //if (argNumberToFind == sum) {
            //System.out.println(array[i] + ", " + array[j]);
            //randomInt1++;
            //randomInt2--;

        //}

And guess what? I got:

Sort and Find Pairs: 20 Find Pairs: 11

Tried several times and the numbers were pretty similar. By removing both loops the runtime for find pairs went to 1. So My guess, maybe the optimization step of the compiler is assuming that the code inside the inner loop doesn't have any effect and thus removes it. The code in Sort and find is a little smarter and so it gets kept.

Now, I tried a different thing, I commented out the increment of randomInt1, but left the sum and if commented,

for (int j = i + 1; j < array.length; j++) {
        //int sum = array[i] + array[j];
        //if (argNumberToFind == sum) {
            //System.out.println(array[i] + ", " + array[j]);
            randomInt1++;
            //randomInt2--;

        //}

and then I got:

Sort and Find Pairs: 42 Find Pairs: 5

Wow, suddenly it got faster! (maybe the compiler replaced the for for the arithmetic calculation of randomInt1 by using the loop bounds?)

My last attempt. You can noticed that this is not a fair comparison, the sort and find have a lot of logic involved, while the find doesn't. It actually does nothing when it find a pair. So to make it apples to apples we want to be sure find pairs actually do something, and lets make sure sort and find do the same extra amount (like adding the same number on both sides of the equation). So I changed the methods to calculate the count of matching pairs instead. Like this:

        System.out.println("\nResults of Find Pairs: \n");                                      
        long randomInt1 = 0;                                                                    
        int randomInt2 = 0;                                                                     
        int count = 0;                                                                          
        for (int i = 0; i < array.length - 1; i++) {                                            
            for (int j = i + 1; j < array.length; j++) {                                        
                int sum = array[i] + array[j];                                                  
                if (argNumberToFind == sum) {                                                   
                    count++;                                                                    
                }                                                                               
            }                                                                                   
        }                                                                                       
        System.out.println("\nPairs found: " + count + "\n"); 

and

    public void sortAndFindPairsOfNumbers(int argNumberToFind, int[] array) {                   
        Arrays.sort(array);                                                                     

        System.out.println("\n\nResults of Sort and Find Pairs: \n");                           
        int startIndex = 0;                                                                     
        int endIndex = array.length - 1;                                                        
        int count = 0;                                                                          

        while (startIndex < endIndex) {                                                         
            int sum = array[startIndex] + array[endIndex];                                      
            if (argNumberToFind == sum) {                                                       
                //System.out.println(array[startIndex] + ", " + array[endIndex]);               
                startIndex++;                                                                   
                endIndex--;                                                                     
                count++;                                                                        
            } else if (argNumberToFind > sum) {                                                 
                startIndex++;                                                                   
            } else {                                                                            
                endIndex--;                                                                     
            }                                                                                   
        }                                                                                       
        System.out.println("\nPairs found: " + count + "\n");                                   
    }

And then got:

Sort and Find Pairs: 38 Find Pairs: 4405

The time for find pairs blowed up! And the sort and find kept in line with what we were seeing before.

So the most likely answer to your problem is that the compiler is optimizing something, and an almost empty for loop is something that the compiler can definitely use to optimize. whilst for the sort and find, the complex logic may cause the optimizer to step back. Your algorithm lessons are find. Here java is playing you a trick.

One more thing you can try is use different languages. I'm pretty sure you will find interesting stuff by doing so!

Answer 2

I removed everything from your sortAndFindPairsOfNumbers method, just kept

Arrays.sort(array);

But still time difference is much more. This means most of the time taken is by sort method.

So your thinking that second approach is Efficient one is not correct. Its all about input size.

If you keep numberRange, lets say, 1000, then SortAndFindPairs will be faster.

Answer 3

As stated by LIuxed, sort operation takes some time. If you invest time in sorting, why do you then not take advantage of the fact that list items are sorted?

If list elements are sorted, you could use a binary search algorithm... start in the middle of the array, and check if you go 1/2 up, or 1/2 down. As a result, you can get faster performance with sorted array for seeking a value. Such an algorithm is already implemented in the Arrays.binarySearch methods.

See https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[],%20int)

You will notice the difference when you sort just once, but seek many times.

Answer 4

Calling the Array.sort(MyArray) method, takes long time because it uses a selection algorithm; this means, the Sort method go through all the array x times ( x= array.lenght) searching for the smallest/biggest value, and set it on top of the array, and so on.

Thats why, using this method takes a long time, depending on the array size.