The Big O

First off, this is a technical blog. My apologies if you came here looking for something a little sexier. Not that Big O Notation can’t be sexy. Depends on what floats your boat or sinks your battleship. Anywho, the following is a little teaser on Big O.

Foreplay

When you take your first few steps learning how to program, something like Big O Notation is the furthest thing from your mind. Learning to code is hard. Period. There is so much to know, and quite frankly, it is daunting. Imagine looking up at the highest peaks of Mt. Everest from the bottom of the mountain. Now imagine that the mountain is always shifting and getting bigger. That’s what it feels like when you start learning. Somewhere along the way (hopefully), your footing will become more secure on the shifting ground and you’ll gain some comfortability in the place of not knowing. Because nobody knows it all. Keep one foot in front of the other and keep climbing. Try to enjoy the ride.

If you went to a bootcamp, there was so much knowledge being pushed into your brain in a few short months. Bootcamps are great, but they just focus on web development. When you graduate and start to prepare for interviews, you begin to hear scary terms that you never heard before. Things like Linked Lists, Big O Notation, Bitwise Operators, Binary Trees, Stacks, Queues, etc. These are all computer science topics and good to know, but unless you are working on high level stuff, you probably don’t have to know all of them. But those pesky interviewers will probably test you on them because they know most bootcamps don’t teach it and because they had to learn it when they got their BS in CS.

Heavy Petting

One of those terms, Big O Notation, is actually very useful to know. When you begin to program, you’re not thinking about how your program will scale if a few thousand or perhaps a million people start to use it. You just learn what a for loop is, then learn you can have nested for loops, and you think everything is grand! Not so fast Kemosabe. This is where Big O Notation and scaling come in. Let’s take a look at how you might write a function to double each element in an array of arrays.


function doubleMe(arrayOfArrays) {
  const doubledArrayOfArrays = [];

  for (let i = 0; i < arrayOfArrays.length; i++) {
    let placeholderArray = []
    for (let j = 0; j < arrayOfArrays[i].length; j++) {
      placeholderArray.push(arrayOfArrays[i][j] * 2);
    }
    doubledArrayOfArrays.push(placeholderArray)
  }

 return doubledArrayOfArrays;
}

doubleMe([[1,2,3], [4,5,6], [7,8,9]];  // [[2,4,6], [8,10,12], [14,16,18]]

This might look all fine and dandy, and when you first learn about nested for loops they might seem like the best thing since sliced bread! But let’s take a look at how this will scale.

We Have Lift Off

The length or size of our arrayOfArrays above is 3. However, since each element of the array is another array the function has to work that much more. Basically, for every item in the array (n for the input size), we have to do n more operations. So n * n == n^2 or O(n^2). The given example might be a little too on the nose being 3^2 is 9. It’s usually not that exact. You might ask, ‘So what’s the big deal? The function only has to run 9 times instead of 3’. Well, everything is groovy if the input is low, but what if it grows to 100 or 1,000 or 1,000,000. You start to get the point. With lower inputs, it’s not a big deal, but as the input grows, so does the time complexity of the function.

BigOn2

Weeeeeeeeeeeeeeeee!!!!

I’m Very Sensitive

Sorry if I got a little too excited. Let’s back up here a bit. Maybe I should start with O(1). Gayle Laakmann McDowell, author of a Cracking the Coding Interview, has a great video about Big O. It’s definitely worth a watch. She gives a great example about a problem South African programmers were having. Their internet connection was super slow and it was taking a long time to transfer data to team members in a different city. So they tried an experiment. They transferred the data to a usb drive and had a carrier pigeon (let’s call him Bob) deliver it to their work mates in the other city. At the same time they were transferring the data through their internet connection. The race between Bob and the internet. Guess who won?

If you said ‘BOB!’, then you are correct. So what does this have to do with Big O? Glad you asked! Bob’s flight in Big O terms is O(1). If it took Bob 30 minutes to get from one office to the other, then no matter what size the file is, it does not change the amount of time it takes him. Whether he’s flying with 10MB or 1TB, it still takes him 30 minutes. So O(1) is a program or function that takes the same amount of time to run no matter how large the input grows.

Time_Complexity

Bob is a low flying bird

Almost There

Revisiting our South African friends, as the size of the data they were transferring (over the internet) grew, the time it took to transfer grew by the same order. This would be O(n) and is linear in time and space. The green line in the graph above represents this. What would this look like as a function? Take my hand and let us find out.


function tripleMe(array) {
  const tripledArray = [];

  for (let i = 0; i < array.length; i++) {
    tripledArray.push(array[i] * 3);
  }

  return tripledArray;
}

tripleMe([1,2,3,4,5]);   // [3,6,9,12,15]

Each element of the array gets worked on once. If our array had 1,000,000 elements, our for loop would run 1,000,000 times. From an input of an array of 1 element to an input of an array with 1,000,000 elements, the time complexity a straight line.

Pillow Talk

There are definitely other elements of Big O to talk about and understand, but I’m spent. I gave a pretty good (in my humble opinion) performance overview of the basics. I hope it was as good for you as it was for me. Sweet dreams buttercup.