O(N) and O(N²) example

twoSum.md

Two Sum Problem – O(N²) vs. O(N) Using HashMap

The Two Sum problem is a classic example where a brute-force solution runs in O(N²), but we can optimize it to O(N) using a hashmap.

1. JavaScript Implementation

Brute-Force Solution (O(N²))

function twoSumBruteForce(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] === target) {
                return true; // Found a pair
            }
        }
    }
    return false; // No pair found
}

// Example usage
const arr = [2, 7, 11, 15];
const target = 9;
console.log(twoSumBruteForce(arr, target)); // Output: true

• Time Complexity: O(N²) because we check all pairs.

Optimized Solution (O(N)) using HashMap

function twoSumHashMap(arr, target) {
    const seen = {}; // Hashmap to store numbers
    for (let num of arr) {
        let complement = target - num;
        if (seen[complement] !== undefined) {
            return true; // Found a pair
        }
        seen[num] = true; // Store number in hashmap
    }
    return false; // No pair found
}

// Example usage
console.log(twoSumHashMap(arr, target)); // Output: true

• Time Complexity: O(N) because we traverse the array once and do O(1) lookups.

---

2. Go Implementation

Brute-Force Solution (O(N²))

package main

import "fmt"

func twoSumBruteForce(arr []int, target int) bool {
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ {
            if arr[i]+arr[j] == target {
                return true // Found a pair
            }
        }
    }
    return false // No pair found
}

func main() {
    arr := []int{2, 7, 11, 15}
    target := 9
    fmt.Println(twoSumBruteForce(arr, target)) // Output: true
}

• Time Complexity: O(N²) because of nested loops.

Optimized Solution (O(N)) using HashMap

package main

import "fmt"

func twoSumHashMap(arr []int, target int) bool {
    seen := make(map[int]bool) // Hashmap to store numbers
    for _, num := range arr {
        complement := target - num
        if _, found := seen[complement]; found {
            return true // Found a pair
        }
        seen[num] = true // Store number in hashmap
    }
    return false // No pair found
}

func main() {
    arr := []int{2, 7, 11, 15}
    target := 9
    fmt.Println(twoSumHashMap(arr, target)) // Output: true
}

• Time Complexity: O(N) because we traverse the array once and perform O(1) lookups in the hashmap.

---

Conclusion

By using a hashmap, we avoid the need for nested loops and reduce the complexity from O(N²) to O(N), making the solution much more efficient.