Understanding Big O Notation Through the Two Sum Problem (For Beginners)

Introduction

Hello everyone! Lately, I've been refreshing my knowledge of algorithms and I thought it would be interesting to put together an article on Big-O notation. I want to both solidify my own understanding and hopefully help others in the process.

What is Big-O?

Big-O notation is a tool for evaluating the efficiency of algorithms and describe the time complexity of algorithms, and understanding it is crucial for programmers. In this article, we will explore the basic concepts of Big O notation through the Two Sum problem.

Big-O notation's "O" stands for "Order of," representing the order of growth in an algorithm's time complexity or space usage.

On the other hand, "Big" is primarily used to illustrate how an algorithm's behavior changes as the size of the problem increases. It signifies the growth rate or order.

For instance, O(n) indicates linear time growth, and O(1) represents constant time complexity, describing specific behaviors of algorithms (I'll provide concrete examples and explanations in the following sections for better clarity).

What is Two Sum?

The Two Sum problem is an algorithm that determines whether the sum of two numbers in an array matches a given target. It's a common algorithm question often asked on programming online platforms like LeetCode or in technical interviews.

Let's assume the following scenario:

Input: nums = [3, 1, 4, 6, 5, 8], target = 10
Output: [4,6]

For the given array of integers nums = [3, 1, 4, 6, 5, 8] and a target integer of 10, selecting the numbers 4 and 6 from the array and adding them results in 10. Therefore, the correct output is [4, 6].

This process of deriving a solution to a computational problem through the use of algorithms is fundamental in programming and problem-solving.

To solve this problem, there are various approaches, but in this article, we'll consider comparing the brute-force method with an approach that utilizes a Hash Map.

Brute Force approach

The first approach is the brute force approach. In this approach, one tries all combinations and finds the one that matches the goal. Let's see the code example:

function twoSumBruteForce(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}
// Big O: O(n^2)

This approach works fine, however, it is inefficient when the input size is large, and we will explore why with Big O notation.

Hash Map approach

Next, let's introduce the Hash Map approach (Hash Table). In this approach, we use a Hash Map to speed up the search process. I'll explain in detail why the Big O notation for this approach is O(n).

function twoSumHashMap(nums, target) {
    const numMap = {};
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (complement in numMap) {
            return [numMap[complement], i];
        }
        numMap[nums[i]] = i;
    }
    return [];
}
// Big O: O(n)

In this approach, we scan through the given array of integers only once and store each element along with its difference from the target in a Hash Map. Specifically, we use the difference as the key in the Hash Map and map it to the index of the corresponding element. After that, we scan through the array again and check whether the difference for each element exists in the Hash Map. This allows us to efficiently determine whether there is a combination of elements that adds up to the target.

Big O Notation O(n)

The reason why the Big O notation for this approach is O(n) is that, in the worst case, we only need to scan through the array of integers once. The operation of saving each element in the Hash Map also takes O(n) time, but overall, this approach has a linear time complexity. Therefore, the Big O notation for the entire approach is O(n).

Conclusion

Understanding and appropriately applying algorithms in practical scenarios can be challenging. However, there are many learning platforms and resources, such as LeetCode, designed for this purpose. If you find this article interesting, I encourage you to explore and delve into the topic on your own.

Thank you for reading!