Big O Notation

If you’ve ever been stuck on which method to use to solve a problem, thinking about complexity is the best starting point. An easy way to express complexity is through Big O notation.

What Is Big O Notation?

In short, Big O notation algebraically describes how complex a program is. This definition is pretty vague, so usually it’s explained with an example such as O(log(n)). Here, n represents the number of inputs your program will take in, and the function “log(n)” represents the complexity of the algorithm with respect to the size of input.

To find the Big O notation complexity of your code, count the operations. When your program loops through code, add n operations. Remember to multiply the number of operations within a loop by the number of times the loop runs. Here’s an example in Python:

If x is our input, then the complexity of this would be 2+n. However, we can remove any constants with Big O Notation, so the complexity of this code would be O(n). This means that the function’s complexity will scale linearly with the size of the input. If the input becomes twice as large, the program becomes twice as complex, and should take about twice as long to run.

How Does This Relate to Competitive Coding?

Let’s say you’re considering a method that has an embedded loop:

If you want to quickly evaluate if this approach will work within the time limit of your problem, think about the complexity. Because there is an embedded loop, the complexity in Big O notation would be O(n²). While this works fine for our input size of 5, it means that the complexity will scale quadratically with input size. If we had 10000 lines of input (not uncommon in a coding competition), our complexity would be massive.

While this program is very simple and wouldn’t take too long to just write and run, harder problems will require much more intricate solutions that take significantly longer to debug and test. By checking the complexity with Big O notation, you can quickly evaluate if your approach will run without wasting effort and time on building and testing the program itself. In short, you can estimate how long your program will take to run without actually running it.

Common Complexities in Big O Notation

While testing different algorithms, you’ll notice that you run into a few very common O complexities. You can see how quickly the complexity scales with input in the following chart:

As you can see, anything above O(n) is going to be pretty bad when run with a large input size. In a programming competition, I’ve rarely seen a functioning solution above an O(nlog(n)) complexity, and those are usually the last few problems.

However, there is one situation where you would use a program with O(n²) complexity, and that is if you’re running out of time and it’s a simple solution. Oftentimes, it’s easy to write a simple but less efficient program, which will get you partial marks on a problem. If you are close to running out of time, it’s often best to play it safe, cut your losses and go with the bad but simple solution. Of course, if you’re practicing, always try to find the most efficient one; this advice only applies during a competition to maximize points.

And that is a brief overview of Big O notation and complexity! I hope this advice is useful in your next coding competition. If you liked this article, you can find my website here and my LinkedIn here.