Big O Notation and Calculating the Runtime of a Function

https://subscription.packtpub.com/video/programming/9781800206878/p2/video2_14/-big-o-notation-and-calculating-the-runtime-of-a-function

by Dominic Myers

JavaScript

// Constant runtime
function log(array) {										// Big O Notation: "0 (1)"
  console.log(array[0]);
  console.log(array[1]);
}
log([1, 2, 3, 4]);
log([1, 2, 3, 4, 5, 6, 7, 8, 10]);

																				// Linear runtime
function logAll(array) {								// Big O Notation: "0 (n)"
  for (var i = 0; i < array.length; i++) {
    console.log(array[i]);
  }
}
logAll([1, 2, 3, 4, 5]);
logAll([1, 2, 3, 4, 5, 6]);
logAll([1, 2, 3, 4, 5, 6, 7]);

																				// Exponential runtime
function addAndLog(array) {							// Big O Notation: "0 (n^2)"
  for (var i = 0; i < array.length; i++) {
    for (var j = 0; i < array.length; j++) {
      console.log(array[i] + array[j]);
    }
  }
}
addAndLog(["A", "B", "C"]); 						// 9 pairs logged out
addAndLog(["A", "B", "C", "D"]); 				// 16 pairs logged out
addAndLog(["A", "B", "C", "D", "E"]); 	// 25 pairs logged out

																				// Logarithmic runtime
function binarySearch(array, key) {			// Big O Notation: "O (log n)"
	var low = 0;
  var high = array.length - 1;
  var mid;
  var element;
  while (low <= high) {
  	mid = Math.floor((low + high) / 2, 10);
  	element = array[mid];
    if(element < key) {
    	low = mid + 1;
    }else if (element > key) {
    	high = mid - 1;
    } else {
    	return mid;
    }
  }
  return -1;
}