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

A Quadratic Problem

Here’s a practical example of where we can replace a slow O(N²) algorithm with a speedy O(N) one.

Let’s say you’re working on a JavaScript application that analyzes the ratings people give to products, where users leave ratings from 0 to 10. Specifically, you’re writing a function that checks whether an array of ratings contains any duplicate numbers. This will be used in more complex calculations in other parts of the software.

For example, the array [1, 5, 3, 9, 1, 4] has two instances of the number 1, so we’d return true to indicate that the array has a case of duplicate numbers.

One of the first approaches that may come to mind is the use of nested loops, as follows:

function hasDuplicateValue(array) {
  for ( ...