Blog

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.

Leave a Reply