A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Trade-Offs Between Time and Space

Here’s a function that accepts an array and returns whether it contains any duplicate values (you may recognize this function from Chapter 4, ​Speeding Up Your Code with Big O​:

def has_duplicate_value(array):
    for i in range(len(array)):
        for j in range(len(array)):
            if (i != j) and (array[i] == array[j]):
                return True

    return False

This algorithm uses nested loops and has a time complexity of O(N²). We’ll call this implementation Version #1.

Here’s a second implementation, Version #2, that employs a hash table and just a single loop:

def has_duplicate_value(array):
    existing_values = {}

    for value in array:
        if value not in existing_values:
 existing_values[value] ...