Looking At Big O Notation With A Few Examples

Introduction (what is Big O)

Big O notation is a way to describe the time complexity of a function. The larger an input is, the longer it will take for the function to run, and this runtime is expressed by Big O. This is different from directly measuring the exact time it takes each function to run; instead of measuring in terms of seconds, Big O gives us an approximation based on the function's input (n).

Main points

O(n) is abstract.
Directly measuring run time is concrete.
The larger the input n is, the larger Big O becomes.
time complexity = how the run time of a function increases as the input increases
Big O often looks at the "worst case" scenario (i.e. the most iterations possible).
Big O and O(n) are synonymous for the purposes of this post.

What can O(n) look like?

I will be going through the following examples of O(n):

O(n)
O(1)
O(n^2)
O(log(n))

Example of O(n) using array iteration

exampleArry = [1, 3, 6, 9, 24]

function findNumber() {
exampleArry.find(element => element > 8)
}

findNumber()
// 9
// This will create an O(n) of n = 4 iterations 
// since find() begins at the left and ends 
// at the right

anotherArry = [1, 5, 7, 9, 20, 130, 260, 340, 400]

function findNumber() {
anotherArry.find(element => element > 350)
}

findNumber()
// 400
// This function uses an O(n) of n = 9 
// iterations, which means the function will 
// theoretically take longer to run

These examples describe Big O by using the function findNumber() to iterate through each element in the exampleArry. The number of iterations is a way to assign a value to n. Therefore, if find() needed to make 3 iterations to find a number (i.e. finding an index of 2), n would equal 3, making O(n) = 3.

If you need a refresher on the find() method, check out a blog I posted comparing different JavaScript iteration methods:

https://dev.to/ericeinerson/comparing-methods-of-array-iteration-in-javascript-1h03

Visual of an O(n) based on exampleArry and anotherArry

This image shows a linear time complexity, which means n is increasing in a linear manner compared to the input. In this example, n = 1, which means O(n) and the input increase at a 1:1 ratio. If the ratio were 2:1 or 1:2, this would still be a linear relationship. These would also still be generalized as O(n), not O(2n) or O(n/2).

Why is Big O important

Big O is a useful tool because figuring out how long a function will take to run may not be that easy. Different languages, running other programs at the same time, one's computer's processing speed, and other factors could make this difficult. Big O is convenient for producing a theoretical model for how long the function should take to run, based on how one's function is written.

Here is how quickly Big O would grow, based on some examples:

O(1)

Sometimes, a function will run at the same speed no matter what the size of the input is. This is called a constant time complexity with regards to Big O. No matter how large the input is, Big O is still going to remain the same value with O(1).

Example of O(1)

exampleArry = [1, 3, 6, 9, 24]

function printNumber(i) {
return exampleArry[i]
}

findNumber(2)
// 6
// This function identifies a single index in exampleArry and returns it. The time needed in order to return the index is just a single step, no matter which index is chosen, hence O(1).

Graph showing O(1) line

O(n^2)

Big O(n^2) describes a time complexity whose run time increases quadratically compared to its input. Therefore, large inputs are going to have extremely large Big O's. This input/time relationship is likely the most important for those working with large inputs because a sizable input could create a slow-running function.

Example of O(n^2)

exampleArry = [1, 4, 5, 1, 6, 4]
function findMatch() {
    for (let i = 0; i < exampleArry.length; i++) {
        for (let j = 0; j < exampleArry.length; j++) {
            if ((exampleArry[i] === exampleArry[j]) && (i !== j) {
                return exampleArry[i]
            }
        }
    }
}

findMatch()
// 1
// This function's worst case involves 36 iterations
// because exampleArry contains 6 indices (6 iterations
// for i each with 6 iterations for j => 36 possible iterations)

Graph showing O(n^2) curve

O(log(n))

This describes a logarithmic increase in time compared to the input and acts in the opposite way as O(n^2). The larger the input for O(log(n)), the less time is added per iteration. Big O(log(n)) would be ideal for larger inputs.

Example of O(log(n))

function findLog(n) {
    count = 0;
    for (let i = 1; i < n; i = i * 2) {

        count++;
    }
    return count
}

findLog(5)
// 2
findLog(10000)
// 13
// This function finds the log of n (not taking into account // decimals). The solution is going to be how many times i
// can be doubled (hence log base 2) until it reaches a value // greater than n.