Big O Notation: Linear Time

Big O Notation is a way to count the number of operations an algorithm will perform given the worse possible scenario. Its useful when trying to visualize how long an algorithm will take to finish computing when given large datasets. In this introduction to Big O we’ll talk about the one of the simplest time complexities, Linear Time.

So imagine you are a bouncer for a high profile club. There’s a line forming in front of you and the club is beginning to open. Your job is to check everyone’s id. If they are over 21 they can enter the club, if they are under 21 they will have to find something else to do with their night.

As a function this could be expressed as:

const lineOfPeople = [{"name": "Tom", "age": 18}, {"name": "Scott", "age": 24} {"name": "Mary", "age": 21}]
function allowEntrance(array){
    for(let i = 0; i < array.length; i++){
        if(array[i].age > 20){
            console.log(`${array[i].name} is ${array[i].age} and can enter`)
        } else {
            console.log(`${array[i].name} is too young to enter`)
        }
    }
}
allowEntrance(lineOfPeople)

And the output could be expressed like this:

Tom is too young to enter
Scott is 24 and can enter
Mary is 21 and can enter

In this example lets say you’re the fastest bouncer in the world and on average it takes you 1 second to look at a person to find their age. That means for filtering through the above line of people it would take you 3 seconds, if filtering through a line of 10 people it would take you 10 seconds, and when filtering through a line of 10,000 people it would take you 10,000 seconds.

This can be expressed as O(n) time complexity, or for each person that joins your line, the time that it takes to completely filter through said line would be expressed linearly:

So for each input it would take a constant amount of time to complete per input.