Hashing vs. Nested Loops

Original Upload: 2024-09-09

Last Updated:

Introduction

This blog shows in python programming language the effectiveness of hashing method versus double nested loops by solving the LeetCode twosum exercise, and achieving a 99% percentile time complexity score. This is a deep-dive that goes into theory, and assumes you know very little to know programming languages and concepts. Thus, it's not a specialized deep-dive, but a horizontal one, meant for particularly curious and inquisitive individuals interested in the workings of computer science concepts.

TwoSum Problem

Given a list of integers and a target sum, find the indices of the two numbers in the list that add up to the target.

                        Input: nums = [2,7,11,15], target = 9
                        Output: [0,1]
                        Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
                    

Nested Loop or 'Brute Force' Approach

The nested loop approach involves checking every possible pair of numbers in the list using double for-loops, one nested within the other.

                        Given an input: [a,b,c,d,e]
                        
                        We need to check each possible pair once:
                        
                        i.e.,
                        
                        [a,b], [a,c], [a,d], [a,e]
                        [b,c], [b,d], [b,e]
                        [c,d], [c,e]
                        [d,e]
                    

While straightforward, this method can be inefficient for large lists.

Time Complexity Analysis

For a list of size n, the nested loop approach performs approximately (n * (n-1) / 2) * 4 operations. For a list of 1000 elements, this results in about 1,998,000 operations.

Hash Table Approach

The hash table approach uses a dictionary to store complement values, allowing for much faster lookups.

Time Complexity Analysis

For a list of size n, the hash table approach performs approximately n * 3 operations. For a list of 1000 elements, this results in only about 3,000 operations.

Memory Considerations

While hash tables offer faster lookups, they do use more memory compared to the nested loop approach. This trade-off between speed and memory usage is a common theme in algorithm design.

Conclusion

The hash table approach demonstrates why it's considered O(n) time complexity, while the nested loop is O(n^2). This significant difference in efficiency becomes even more pronounced as the size of the input grows.

Hashing vs. Nested Loops

Introduction

TwoSum Problem

Nested Loop or 'Brute Force' Approach

Time Complexity Analysis

Hash Table Approach

Time Complexity Analysis

Memory Considerations

Conclusion

Actual Content Coming Soon.