Considering Optimization and Time Complexity with JS Algorithms

After having recently graduated from Flatiron’s Full Stack Immersive Program, I am now armed with a pretty impressive toolbox of languages, frameworks, and methods to take into my new world as a software developer. My goal now is to understand those tools even better, and to reach that level of expertise where I know exactly the right tool to use for each particular situation.

I was recently presented with a whiteboarding question that, on its surface, seemed rather simple: Given an array of positive integers, write a function that returns true if any element in that array is the double of any other element. If not, return false. So, if I were given the array [3, 4, 6] my function should return true, because 6 is the double of 3. Given the array [4, 5, 7] my function should return false, because no number in that array is the double of any other number in the array.

Thinking through the problem logically, my initial plan was to…

1. Determine the double of each number in the array, then
2. Check to the see if the array includes any of the doubles.

This is a fairly straightforward plan, and here’s what it looks like in code:

This function uses a while loop to iterate through each number in the array (array[i]), then a conditional (if statement) uses the .includes() method to check to see if that number’s double (array[i] * 2) is included in the array. If it finds the double, the function breaks out of the loops and returns true. If not, the while loop continues to run through the entire array, and with each iteration of the while loop the .includes() method runs through the entire array. When no double is found, the loops conclude without returning anything, at which point the function returns false.

My includesDouble function is easy to read, and easy to understand, but let’s consider time complexity and Big O notation for a moment…

Time complexity simply refers to the amount of time it takes an algorithm, or set of code, to run.

Time complexity is most often measured in Big O notation. If you’re unfamiliar with Big O, here’s a great article that breaks it down in simple terms. For my includesDouble function, n, which is the size of the input, would be 3 — if we were to use either of our earlier arrays ([3, 4, 6] OR [4, 5, 7]). So we begin with O(n) = 3.

When considering time complexity, best practice is to calculate the worst case scenario. Looking at our two arrays, that would be [4, 5, 7], because we know that this array does not include a double, so both loops (our while loop and .includes()) will run completely through the entire array because there is no true case that will break them out of the loops. Okay, so if [4, 5, 7] runs through the while loop we have a linear run time of O(n) = 3, because our while loop runs once for each element in our array (once for 4, twice for 5, and a third time for 7). However, for each iteration of our while loop we have a nested loop that also runs — .includes().

Beware of nested loops — this is where your time complexity, or Big O notation, begins to grow exponentially.

Let me explain…

If our array includes the numbers 4, 5, and 7, on our first iteration through (where array[i] = 4), our .includes() method is going to run through each item in our array to see if the array includes 8 (array[i] * 2). It will then do the same thing for all of the other numbers in our array (5, then 7).

To make things more explicit, our JavaScript engine would run through the following steps:

1. For the number 4, does 4 equal 8?
2. For the number 4, does 5 equal 8?
3. For the number 4, does 7 equal 8?
4. For the number 5, does 4 equal 10?
5. For the number 5, does 5 equal 10?
6. For the number 5, does 7 equal 10?
7. For the number 7, does 4 equal 14?
8. For the number 7, does 5 equal 14?
9. For the number 7, does 7 equal 14?

Because we have a nested loop, our Big O notation goes from O(n) = 3 to O(n²) = 3². A Big O of 3 vs. a Big O of 9 isn’t that great a difference, but remember that with time complexity, we want to consider the worst case scenario — what if our array was a thousand numbers long? All of a sudden, O(n) = 1000, turns to O(n²) = 1,000,000 with a nested loop! Now that’s a big difference! Imagine if our array contained a million numbers!!!

So, is there a way to solve this problem with an algorithm that doesn’t use a nested loop?

I’m so glad you asked, because the answer is yes.

Enter the hash table…

A hash table is simply a data structure that is associative — it maps keys to values.

If you’ve been coding for at least a little while, you’ll have seen this type of data structure before — (hash tables are also called objects in JavaScript and hashes in Ruby).

‘That’s really great,’ you’re probably thinking — ‘but how does a hash table about cats solve the algorithm problem above?’

Let me share with you the solution first, and then we’ll go through it step by step.

Again, we’ll use our previous array ([4, 5, 7]) to walk through this function.

On the first line inside the function, notice that I’m declaring a new variable, doubles, and setting it equal to an empty hash table ({}). We’re going to build out this hash table using the elements from our array as we go.

Just as before, we’ll start with a while loop (O(n) = 3). Inside the while loop, I’m going to use the numbers in my array to make keys for my new hash table (doubles[array[i]] = ‘cats are so cool’). We know that with this array, our while loop will return without returning true, so after our while loop finishes, we’ll have a hash table that looks like this:

Cats ARE really, really cool.

Notice that, even though they’re full of wisdom, the values that I’ve set my keys to don’t really matter. The keys are the key.

Now let’s look at the second line in our while loop — here we have another conditional — only this time we’re not using .includes(). Instead, we’re checking the keys in our hash table against our current number to see if there is a key that is already double, or half of, our current number. If that key already exists, then we know that we’ve found a double!

To break it down more explicitly…

1. Our first run through the while loop (with array[i] = 4) produces doubles = {4: ‘cats are so cool’}. It runs through the conditional without returning anything because doubles has only one key, 4, and does not include a key of 8 or 2.
2. The second run through the while loop (with array[i] = 5) adds a new key to doubles — {4: ‘cats are so cool’, 5: ‘cats are so cool’}. Again it passes through the conditional without matching a key.
3. Finally, our last run through produces doubles = {4: ‘cats are so cool’, 5: ‘cats are so cool’, 7: ‘cats are so cool’} and exits the conditional and the while loop without matching a key.
4. Because there was no positive case to break us out of the while loop, our function returns false!

Notice anything?

We wrote a function that does what it needs to do without using a nested loop!

The Big O notation for this version of our includesDouble function is just O(n) = 3. If we had an array of a million numbers, Big O would be O(n) = 1,000,000. Compare that with O(n²) = 1,000,000,000,000 (one trillion) and we’ve shaved off a huge chunk of our function’s run time!

Ahhh… isn’t life good?

As great as our new function is, it does pose some trade-offs — first of all, our second function is a little harder to understand than our first. If you’re concerned about readability (maybe you’ve got a bunch of newbie programmers on your staff, like me) and you know that n is never going to be astronomically long, you may prefer to stick with the first option. Also, notice that in the second function we also create a brand new variable (doubles = {}). This means that your computer now has to create and set aside a specific place in memory to store that new piece of data. If you’re worried about memory space, and you know that n will always be a reasonable length, again you may choose to go with option #1.

There’s definitely more than one way to skin a cat…