Two solutions to 2-sum

Question

I have written a solution for two sum problem in variation. first is simple with two loops and another one is one loop and hash map.

But I wonder why the simple solution is faster than the efficent solution

simple solution -

func TwoSum(arr []int, s int) [][]int {
    var sum [][]int
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i]+arr[j] == s {
                sum = append(sum, []int{arr[i], arr[j]})
            }
        }
    }
    return sum
}

Hashmap solution -

func TwoSum1(nums []int, target int) [][]int {
    var r = make([][]int, 0)
    var m = make(map[int]int, 0)
    for p, i := range nums {
        j := target - i
        if pos, ok := m[j]; ok {
            if pos != p {
                r = append(r, []int{j, i})
            }
        } else {
            m[i] = p
        }
    }
    return r
}

also, I have written Benchmark

type args struct {
    arr []int
    s   int
}

var tests = []struct {
    name string
    args args
    want [][]int
}{
    {
        "One",
        args{[]int{3, 5, 2, -4, 8, 11},
            7,},
        [][]int{{5, 2}, {-4, 11}},
    },
}



func BenchmarkTwoSum(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, tc := range tests{
            TwoSum(tc.args.arr, tc.args.s)
        }
    }
}

BenchmarkTwoSum-4 3000000 382 ns/op

func BenchmarkTwoSum1(b *testing.B) {
        for i := 0; i < b.N; i++ {
            for _, tc := range tests{
                TwoSum1(tc.args.arr, tc.args.s)
            }
        }
    }

BenchmarkTwoSum1-4 2000000 561 ns/op

Answer 1

When you ask if your first solution is faster, if you are talking about theory it isn't faster. To understand why you need to understand the the difference between big O complexity and actual run time. For the purposes of this question, it is important only that you realize that big O complexity does not guarantee that a piece of code with O(n^2) run time will run faster than O(n) for all inputs merely that for some very large inputs O(n^2) will be faster. More exactly, Big O complexity merely talks about the growth rate of a function at really large values. Without getting into it too much you can imagine that the if we have x^2 and 1000000x, I can guarantee that at some input x^2 will surpass 1000000x. Similarly, if I have x^2 + x I can guarantee that at some point the x^2 term will be so much bigger than the x term that the any increase in in our input will essentially just increase the function by approximately x^2. If that doesn't make sense, then I would suggest brushing up on big O here https://medium.com/karuna-sehgal/a-simplified-explanation-of-the-big-o-notation-82523585e835 .

Now for your problem, the big O complexity of the hash map based solution is O(n) the big O for the brute force double loop solution is O(n^2). Now as mentioned about big O does not guarantee that an O(n^2) piece of code will always run faster that an O(n) piece of code for all inputs. Big O is a mathematical guarantee only for large inputs. All big O says is that for some large input O(n^2) will be faster O(n). Let me give you a specific example of why despite a greater big O the double loop solution might be faster for a constrained input. let's say that your two loop solution runs in n^2 time exactly and your hash map solution runs in 1000000000*n time. Well technically your hash map solution would benchmark much much slower for reasonable sized inputs, but eventually if the input were big enough then your hash map solution would run faster. Now, maybe you only care about the performance for a constrained sample size. That's great. This is why you will always have to run a benchmark to compare solutions. Big O is not meant as a tool to guarantee that a certain piece of code will run faster for all inputs, only as a tool to theoretically reason about performance for extremely large inputs. Knowing the time complexity in O notation, won't give you any sort of idea what might be faster for a given constrained input size. That's why in the real world, understanding big O is important, but it is also very important to run performance benchmarks based on how big you actually expect your input to get. I've repeated this central theme in different ways throughout this post but I will summarize again here Big O only guarantees run time for some extremely large input (think as the limit of your input goes to infinity) it says absolutely nothing about some constrained input. I could reasonably come up with a Big O problem where an O(n^2) piece of code would never run faster than an O(n) piece of code given the constrained of the amount of memory on your computer. Basically, use big O to get a general idea of run time when writing your code, and then if you see some performance issues benchmark to find improvements.

Now in the case of this question, someone with a little more understanding of what's actually happening in Go might be able to tell you exactly what operation is making your hash map solution slower for those inputs. My guess... when you call make(map[int]int, 0) you are allocating space on the heap, which is likely taking a good amount of time.