Performance on two different implementation on two sum problems

Question

I have two different solutions for classic two sum problem, one is using the hashmap to traverse the list once, and another one is using two indexes and a sorted array to find the solution. The time complexity of using hashmap is O(n), and O(nlog(n)) on the other method, however, the running time report shows using the sorted array is faster than using map. Why?

Method 1: Using hashmap

public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(target - numbers[i])) {
            result[1] = i + 1;
            result[0] = map.get(target - numbers[i]);
            return result;
        }
        map.put(numbers[i], i + 1);
    }
    return result;
}

Method 2: using two indexes and a sorted array

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] sorted_nums = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            sorted_nums[i] = nums[i];
        }
        Arrays.sort(sorted_nums);

        int begin = 0;
        int end = sorted_nums.length - 1;
        while(begin < end) {
            if(sorted_nums[begin] + sorted_nums[end] == target)
                break;
            else if(sorted_nums[begin] + sorted_nums[end] > target)
                end--;
            else
                begin++;
        }

        int[] result = new int[2];
        int idx = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == sorted_nums[begin] || nums[i] == sorted_nums[end])
                result[idx++] = i;
        }
        return result;
    }
}

Answer 1

It depends on the input array size - the overhead ob boxing/unboxing and additional memory overhead might be too big to "be erased asymptotic runtime complexity"

I wanted to test what is happening here, and it seems that the slow part is GC when you have a lots of runs on smaller inputs. Then the GC overhead is bigger than benefit of better asymptotic complexity.

My code to test

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class TwoSum {

    //run with -Xmx1g
    public static void main(String... args) {

        for (int sampleSize = 1; sampleSize < 1000; sampleSize*=5) {
            for (int size = 10; size <= 40_000_000; size *= 10) {
                System.gc();
                int[] numbers = new int[size];

                int a = 0;
                int aa = 1;
                for (int i = 0; i < size; i++) {
                    numbers[i] = a;
                    a += aa++;
                }

                Random r = new Random(42);
                int[] t = new int[sampleSize];
                for (int i = 0; i < sampleSize; i++) {
                    t[i++] = numbers[r.nextInt(size)] + numbers[r.nextInt(size)];
                }
                long b = System.currentTimeMillis();
                for (int i = 0; i < sampleSize; i++) {
                    twoSumMap(numbers, t[i]);
                }
                long c = System.currentTimeMillis();
                for (int i = 0; i < sampleSize; i++) {
                    twoSumArray(numbers, t[i]);
                }
                long d = System.currentTimeMillis();

                System.out.println(
                    "On size: " + size + " MAP takes: " + (c - b) + " ARRAY takes: " + (d - c) + " with sample size: " + sampleSize);
            }
        }
    }

    public static int[] twoSumMap(int[] numbers, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                result[1] = i + 1;
                result[0] = map.get(target - numbers[i]);
                return result;
            }
            map.put(numbers[i], i + 1);
        }
        return result;
    }

    public static int[] twoSumArray(int[] nums, int target) {
        int[] sorted_nums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            sorted_nums[i] = nums[i];
        }
        Arrays.sort(sorted_nums);

        int begin = 0;
        int end = sorted_nums.length - 1;
        while (begin < end) {
            if (sorted_nums[begin] + sorted_nums[end] == target)
                break;
            else if (sorted_nums[begin] + sorted_nums[end] > target)
                end--;
            else
                begin++;
        }

        int[] result = new int[2];
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == sorted_nums[begin] || nums[i] == sorted_nums[end])
                result[idx++] = i;
        }
        return result;
    }
}

output:

On size: 10 MAP takes: 0 ARRAY takes: 1 with sample size: 1
On size: 100 MAP takes: 0 ARRAY takes: 0 with sample size: 1
On size: 1000 MAP takes: 1 ARRAY takes: 0 with sample size: 1
On size: 10000 MAP takes: 2 ARRAY takes: 1 with sample size: 1
On size: 100000 MAP takes: 24 ARRAY takes: 4 with sample size: 1
On size: 1000000 MAP takes: 75 ARRAY takes: 90 with sample size: 1
On size: 10000000 MAP takes: 15 ARRAY takes: 862 with sample size: 1
On size: 10 MAP takes: 0 ARRAY takes: 0 with sample size: 5
On size: 100 MAP takes: 0 ARRAY takes: 0 with sample size: 5
On size: 1000 MAP takes: 0 ARRAY takes: 0 with sample size: 5
On size: 10000 MAP takes: 3 ARRAY takes: 0 with sample size: 5
On size: 100000 MAP takes: 107 ARRAY takes: 10 with sample size: 5
On size: 1000000 MAP takes: 144 ARRAY takes: 309 with sample size: 5
On size: 10000000 MAP takes: 45 ARRAY takes: 4167 with sample size: 5
On size: 10 MAP takes: 0 ARRAY takes: 0 with sample size: 25
On size: 100 MAP takes: 0 ARRAY takes: 0 with sample size: 25
On size: 1000 MAP takes: 1 ARRAY takes: 0 with sample size: 25
On size: 10000 MAP takes: 19 ARRAY takes: 2 with sample size: 25
**On size: 100000 MAP takes: 643 ARRAY takes: 36 with sample size: 25**
On size: 1000000 MAP takes: 902 ARRAY takes: 1516 with sample size: 25
On size: 10000000 MAP takes: 434 ARRAY takes: 20626 with sample size: 25
On size: 10 MAP takes: 0 ARRAY takes: 0 with sample size: 125
On size: 100 MAP takes: 1 ARRAY takes: 0 with sample size: 125
On size: 1000 MAP takes: 7 ARRAY takes: 1 with sample size: 125
On size: 10000 MAP takes: 104 ARRAY takes: 9 with sample size: 125
**On size: 100000 MAP takes: 2499 ARRAY takes: 148 with sample size: 125**
On size: 1000000 MAP takes: 3282 ARRAY takes: 7485 with sample size: 125
On size: 10000000 MAP takes: 1966 ARRAY takes: 102934 with sample size: 125
On size: 10 MAP takes: 0 ARRAY takes: 0 with sample size: 625
On size: 100 MAP takes: 3 ARRAY takes: 1 with sample size: 625
On size: 1000 MAP takes: 34 ARRAY takes: 4 with sample size: 625
**On size: 10000 MAP takes: 485 ARRAY takes: 42 with sample size: 625**
**On size: 100000 MAP takes: 12807 ARRAY takes: 734 with sample size: 625**
On size: 1000000 MAP takes: 16113 ARRAY takes: 37191 with sample size: 625