Big O Notation: Powers of N

#algorithms #bigo #beginners

Last week we talked about some of the basics of Big O Notation. We also briefly touched on some examples of O(1) and O(n). This week we’re going to cover Big O complexities that are increasing powers of N.

First however, let’s quickly review O(1) and O(n).

O(1) means that the time or space complexity of an algorithm does not increase as the size of the input increases.

O(n) means that the time or space complexity of an algorithm increases linearly as the size of the input increases.

Time Complexity: O( n^2 )

When learning about O(n) time complexity, we looked at a function called doubleArrayValues(array) that used a for loop to iterate through an array and double the value at each index location. But what kind of a function would have a time complexity of O( n^2 )? Let's look at this example.

const printPairs = (arry) => {
    for(let i=0; i < arry.length; i++){
        for(let j=0; j < arry.length; j++) {
            console.log(arry[i] + "," + arry[j])
        }
    }
}

This function uses a for loop nested inside another for loop to print every possible pairing of the input array's values. Now this is not the most efficient way to do this since it will print some pairings more than once, but let's not worry about that right now.

What is the Big O complexity of this function? Let's look at how many iterations take place to find out.

The inner for loop iterates over the entire array. So if the array has a length of N, the inner loop will execute its code N times. However, the outer for loop also executes N times since it will run until i is equal to the length of the array.

If we have a block of N executes that is being executed N times, that gives us:

N x N = N^2

Since the code has n^2 executions we say that it has a Big O time complexity of O( n^2 ).

Time Complexity: O( n^3 ), O( n^4 ), etc.

As you can imagine, the more nested loop you add, the higher the power of N becomes. So,

This would have a Big O time complexity of O( n^3 ):

const printGroupsOfThree = (arry) => {
    for(let i=0; i < arry.length; i++){
        for(let j=0; j < arry.length; j++) {
            for(let k=0; k < arry.length; k++) {
                console.log(arry[i] + "," + arry[j] + "," + arry[k])
            }
        }
    }
}

This would have a Big O time complexity of O( n^4 ):

const printGroupsOfFour = (arry) => {
    for(let i=0; i < arry.length; i++){
        for(let j=0; j < arry.length; j++) {
            for(let k=0; k < arry.length; k++) {
                for(let m=0; m < arry.length; m++) {
                    console.log(arry[i] + "," + arry[j] + "," + arry[k] + "," + arry[m])
                }
            }
        }
    }
}

For every loop that is nested inside the inner most loop, you are adding 1 to the power of N iterations and therefore the Big O complexity is also increased by one power of N.

Space Complexity: O( n^2 ), O( n^3 ), O( n^4 ), etc.

Recognizing a function with a Big O space complexity that is multiple powers of N is similar to the time complexity. But remember, with space complexity we are talking about how much memory the function is using. Believe it or not, all of the examples we have looked out so far all have a space complexity of O(1). That's right! Even the last one with a time complexity of O( n^4 ) has a space complexity of O(1). This because all the above functions simply access existing locations in memory. They do not allocate new locations in memory.

However, what if these functions did allocate memory?

const printGroupsOfFourAndReturn = (arry) => {
    const result = [];
    for(let i=0; i < arry.length; i++) {
        for(let j=0; j < arry.length; j++) {
            for(let k=0; k < arry.length; k++) {
                for(let m=0; m < arry.length; m++) {
                    result.push(`${arry[i]}, ${arry[j]}, ${arry[k]}, ${arry[m]}`);
                    console.log(arry[i] + "," + arry[j] + "," + arry[k] + "," + arry[m])
                }
            }
        }
    }
    return result;
}

In this example the function is pushing every group of four values onto a new array as well as printing those values. Since a new memory location is allocated every time the code in the inner most loop is executed and that code is executed N x N x N x N times, or N^4 times, we know that the space complexity of this function is now O( n^4 ).

Bonus Topic: O(ab)

Be careful not immediately declare something to be O( n^2 ) or O( n^3 ) the moment you see nested loops. What if the those loops iterate over different arrays?

const printPairs = (arryA, arryB) => {
    for(let i=0; i < arryA.length; i++){
        for(let j=0; j < arryB.length; j++) {
            console.log(arryA[i] + "," + arryB[j])
        }
    }
}

Now our function is printing pairs of values from two different arrays. As before, let's determine how many iterations are taking place.

The inner for loop executes its code B times, where B is equal to the length of arryB. The outer for loop executes the inner for loop A times, where A is equal to the length of arryA.

So, A x B = AB, which is not equal to N^2.

This is because arrayA and arrayB could be different lengths. It's an easy mistake to make, so make sure you're watching out for it.

Conclusion

Let's recap what we've learned,

Nested loops that iterate over the entire length of one array have a Big O time complexity of O( n^x ), where x is equal the number of nested loops including the outer most loop.
If the inner most loop is allocating new memory locations, these nested loops also have a Big O space complexity of O( n^x ), where x is equal the number of nested loops including the outer most loop.
If watch out for cases where different levels of the nested loops are iterating over different arrays. These nested loops most likely do not have a Big O complexity that is a power of N.