Is it hot or not? Let's check....

Introduction

Warning!! The following material is usually disolved in 4 semesters or more in order for students to really grasp this. So do not get frustrated if you don't get it at first.

Big O

Big O is the way we analyze how efficient algorithms (or code in this case)are, without getting too mired in the details. We can model how much time any function is going to take given n inputs, but in the reality we're interested in the order of magnitude of the number and necessarily of the exact figure.

Example: I don't particularly care if a function takes 300 miliseconds versus 330 miliseconds given 1,000 inputs, but I do care if it takes 300 miliseconds versus 30 seconds. This would be a difference in an order of magnitude, or basically we're saying we only care if the difference is pretty large.

Enter Big O. Think of O as a vacuum that sucks in all the uninportant information and just leaves you with the important stuff. Let's look at a purely mathematical perspective for a second. Say we have the equation 3x² + x + 1. If we plug in 5, the first item will be 75, the second 5 and the third would be 1. In other words, most of the piece of the pie comes from the first term, to the point we can just ignore the other terms. If we plug huge numbers it becomes even more apparent. IE if we do 5,000,000. the first term is 75,000,000,000,000 the second is 5,000,000 and the last 1. A huge gap.

Hence this is what Big O does; We ignore the little parts and concentrate on the big ones. Kepping with 3x² + x + 1, the Big O for this equation would be O(n²) where O is just absorbin all the other fluff (including the factor on the biggest term). Just grab the biggest term. So for n terms it's going take us nn* to go though our inputs. So let's see how to derive this from an algorithm

function crosAdd(input) {
	var answer = [];
	for (var i = 0; i < input.length; i++) {
		var goingUp = input[i];
		var goingDown = input[input.length - 1 - i];
		answer.push(goingUp + goingDown)
  }
	return answer;
}

This is O(n) because we go though all inputs once in a loop

function find(needle, haystack) {
	for (var i = 0; i < haystack.length; i++) {
		if (heystack[i] === needle) return true
	}
}

Still O(n). Unless we say otherwise we're assuming worst case scenario. In this worst case, the needle would be the last element.

function makeTuples(input) {
	var answer = [];
	for(var i=0; i < input.length; i++) {
		for(var j=0; j < input.length, j++) {
			answer.push(input[i], input[j]);
		}
	}
	return answer;
}