big-o.md

##A Bluffer’s Guide to Big-O Notation

What is it? Big-O Notation is a way to roughly estimate the growth in runtime for a given operation as the input it operates on increases in complexity. You’ll often hear it referred to like, “this function has a runtime of O(n log n).”

Can you explain that simpler? Sure. Let’s imagine a function that takes in a single array (of indeterminate length) as a parameter, does something with its contents, and returns some kind of value. What Big-O is intended to convey is how dramatically the time it takes to execute the function increases as the size of the input array increases.

Let’s make this real! In our imaginary world, the environment that’s running our code takes exactly 1 millisecond to check the value of any variable or at any index of an array, and another 1 millisecond to the set the value of any variable or at any index of an array. (This is artificial, but it at least allows us to count things.)

If we have a function that takes in an array, loops through the array to find the highest value, and returns that value, it would look something like this:

var highestValue = function (input) {
	var highestSoFar = input[0]
	
	for (var i = 1; i < input.length; i++) {
		if (highestSoFar < input[i]) {
			highestSoFar = input[i]
		}
	}
	
	return highestSoFar
}

Imagine we called that function with a simple, three-member array: highestValue([15, 20, 12]). We can list the get and set operations that the function executes.

1. Get the value at index 0 of the input array
2. Set highestSoFar to that value (15)
3. Set the value of i to 1
4. Get the length of the input array (3) -- it's greater than i so execute the loop
5. Get the value of highestSoFar (15)
6. Get the value of i (1)
7. Get the value of index 1 of the input array
8. Set the value of highestSoFar to the value of input[1] (20)
9. Set the value of i to 2
10. Get the length of the input array (3) -- it's greater than i so execute the loop again
11. Get the value of highestSoFar (20)
12. Get the value of i (2)
13. Get the value of index 2 of the input array (12) -- it's less than 20 so skip the if block
14. Set the value of i to 3
15. Get the length of the input array (3) -- it's equal to i so break out of the loop
16. Get the value of highestSoFar (20) and return it.

In our imaginary environment, that function's execution will take 16 milliseconds. That might seem like a lot at first glance, but it's really not -- computers are happy to do simple instructions quickly for us. What's notable is that a few of those operations are setup, and will only ever happen once (the first three, and the last one).

Each time running through the loop takes either 5 or 6 operations:

• check the length of the array
• get the value of highestSoFar
• get the value of i
• get the value of index[i]
• maybe set the value of highestSoFar to index[i]
• increment i

The point of Big-O notation is not to calculate a specific number of instructions, but to recognize that we could throw an array with a thousand members (instead of 3) into this function, and that the loop would execute just those same 5 or 6 instructions for one.

In our imaginary world of extraordinarily slow computers, this will cause the program to run for ~5500 milliseconds. But, that's about 5.5ms per member in the input array. Our sample three-member array took 16 instructions... or about 5.5ms per member. (Precision isn't super-important here, scale is.)

Therefore, our function is understood to run in linear time, which is represented in Big-O land as O(n). In big words, you could say "as the complexity of the input increases, the runtime of the function scales linearly."