Big O Definition and Finding Big O from Four Semesters of Computer Science in 5 Hours by Brian Holt
Posted on August 3, 2020 in JavaScript by Matt Jennings
Big O Definition
In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows (from Wikipedia).
Finding Big O Examples
In the code below the big O is n because there is only one loop.
function crossAdd(input) { var answer = []; // In broad strokes the big O time complexity // is O(n) because we go through all the inputs once in a loop. // Or to put it another way the big O is "n". 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; }
In the code below the big O is n2 because there is one loop nested in another loop.
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; }
If there are no loops and you do something and exit/return then it’s said we’re doing it in contact time, or o(1). An example is below (this means there’s no loops in code):
function constTimeExample() { var arr = [1, 2, 3]; return arr[2]; }
You can also have o(log n) if a code employs a divide-and-conquer strategy (often recursive). This means as you add more terms, the increase in time as you add input diminishes.