A Common-Sense Guide to Data Structures and Algorithms

Trade-Offs Between Time and Space

In Chapter 4, ​Speeding Up Your Code with Big O​, we wrote a JavaScript function that checked whether an array contained any duplicate values. Our first version looked like this:

function hasDuplicateValue(array) {
    for(var i = 0; i < array.length; i++) {
        for(var j = 0; j < array.length; j++) {
            if(i !== j && array[i] == array[j]) {
                return true;
            }
        }
    }
    return false;
}

It uses nested for loops, and we pointed out that it has a time complexity of O(N²).

We then created a more efficient version, which looked like this:

function hasDuplicateValue(array) {
    var existingNumbers = [];
    for(var i = 0; i < array.length; i++) {
        if(existingNumbers[array[i]] === undefined ...