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.

Cool Shortcuts in JS

After learning Ruby, getting stuff done in Javascript can seem much harder. Many methods in Ruby, such as sort, are just a dot notation away. However, in JS you have to write out the whole function. Check it…

# Ruby
numbers = [2, 5, 6, 11, 1, 23, 3]
numbers.sort!
# numbers = [1, 2, 3, 5, 6, 11, 23] Not bad at all!
# That was so easy. Let's try it with names....

names = ['Martha', 'Tony', 'Sarah','Bob', 'Clara']
names.sort!
# names = ["Bob", "Clara", "Martha", "Sarah", "Tony"]
# Woah! It's the same!

// JS
let numbers = [2, 5, 6, 11, 1, 23, 3]
numbers = numbers.sort((a, b) => a - b)
// Well that's not so bad
// Let's try it with names

let names = ['Martha', 'Tony', 'Sarah','Bob', 'Clara']
names = names.sort((a, b) => {
  if (a < b) {
    return -1;
  } else if (a > b) {
    return 1;
  } else {
    return 0;
  }
});
// Yuck. Quite a bit more verbose

Well, unfortunately there are just some things in JavaScript that are the way they are. Like my Scottish father-in-law says, “You cannot fart against thunder”. Some things you just have to accept. Sometimes, you (or people that make the thunder) can change it. ES6 has brought some cool changes that have made programming in JS much more fun. I’ve been messing around with some cool shortcuts that you can use to give your fingers a bit of a break. Some of these were already available pre-ES6.

First let’s take a look at flattening an array of arrays.

# Just for fun I'll include the Ruby magic

arrays = [1, [2, 3], [4, [5, 6]], 7]
arrays.flatten!
# [1, 2, 3, 4, 5, 6, 7] - Too easy

// Pre ES6
var arrays = [1, [2, 3], [4, [5, 6]], 7];
var flattenedArrays = [].concat.apply([], arrays);
// [1, 2, 3, 4, 5, 6, 7]
// Not horrible, but the spread operator makes it even better...

const arrays = [1, [2, 3], [4, [5, 6]], 7];
const flattenedArrays = [].concat(...arrays)
// Not a huge difference, but - Less typing = Happier coder 

Ok that wasn’t a huge deal. Here are some examples using operands. Thanks to these wonderful humans for bringing them to my attention.

var number = 1,
  string = "1",

// How would you normally change number to a string? Personally, I'd use the  .toString() method

number.toString()
// "1" 
// But this is more fun...
number + ""  // "1"
// I like

// How bout changing that string to an integer?
// A little parseInt() shall we?

parseInt(string) // 1
// The following is much more succinct

+string // 1
// Shiiiiit. That's cool.

How bout finding the max/min from an array. Well the Math prototype does not accept an array as it’s arguments.

// Pre-JS6
const numbers = [8, 7, 55, 4];
Math.max.apply(null, numbers) // 55
Math.min.apply(null, numbers) // 4
// JS6
Math.max(...numbers)  // 55
Math.min(...numbers)  // 4
// Very nice!

# Just for S & G's - Ruby
numbers.max  # 55 - beautiful

The spread operator makes this possible by spreading the values in the array out into arguments of the math functions. Not quite the magical abstractness of Ruby, but cool nonetheless! There are of course libraries like lodash that fill in some of the cracks, but there are always new things to discover about a language. The never ending mountain is waiting to be climbed. She is forever shifting and you can never reach the top. You just have to learn to love climbing. And remember…you cannot fart against thunder (in a very broad Scottish accent). That man has some stories.