Big O Notation

o.js

/*
  Big O notation describes the complexity of an algorithm by denoting how long it
  will take to run in the worst-case scenario. It gives an asymptotic upper bound.

  O(1)
  Algorithm will always take same time to execute regardless of input
*/

function isNumberOne(number) {
  return number === 1;
}

/*
  O(n)
  Complexity increases linearly in direct proportion to the number of inputs
*/

function areNumbersEqual(numArr, numToCompare) {
	numArr.forEach((num) => {
		if (num === numToCompare) {
			return true;
		}
	});
	return false;
}

/*
  O(n^2)
  Complexity is directly proportional to square of input size.
	_Example is assuming a sorted array_
*/

function arrContainsDuplicates(numArr) {
	for (let outer = 0; outer < numArr.length; outer++) {
		for (let inner = 0; inner < numArr.length; inner++) {
			if (outer !== inner) {
				return numArr[outer] === numArr[inner] ? true : false;
			}
		}
	}
	
	return false;
}

/*
  O(2^n)
  Complexity doubles for every element in the input. Growth is exponential.
*/

function fibonacci(num) {
	return num <= 1 ?
		num :
		fibonacci(num - 2) + fibonacci(num - 1);
}

/*
  O(log n)
  Complexity increases logarithmically as the input size increases.
  Scales well as larger inputs are less likely to impact performance.
*/

// BINARY SEARCH