Big O

Preparing for technical interviews is a given in the Software Engineering field, especially for your first jobs. If you don’t have a Computer Science background this can be especially daunting since preparing for interviews involves working on algorithms and understanding complex data structeres. As in coding when solving an algorithm there are different approaches to solving a problem. Normally when programming there isn’t a right or wrong answer different people have different critical thinking skills, thus different ways of solving problems.

However when solving algorithms a solution can be objectively better to another, and we can figure out which approach was better using Big O notation.

The first impression you might have to see if your code is better might be time. The time it takes to run an algorithm and give you back the answer. The issue here is that everyone has a different work set up, you can either be working on a PC, or a laptop and every machine has different specs. These specs affect how fast your algorithm is, due to the performance of your machine on any given day. So instead of using time as a rule of thumb to give your code a “grade” we count the number of operations.

As an example we have two different solutions to a function that adds all of the numbers up to “n”, for example if we inputed 5 into the function we would get back

1 + 2 + 3 + 4 + 5 = 15

This function uses a mathematical formula to get the result.

The second function uses a more familiar approach we as programmers might use

As we can see the first function only has 3 operations regardless of the number we input into the function. But the second more familiar function has “n” additions. Which means that if we inputed 1,000,000 into our function we’d have 1,000,000 additions!

The second function has operations based on 5n +2 (which are 5 operations that depend on “n” and 2 fixed operations, the assignment of the total variable and the assignment of i in the loop). In comparison to the first function this is quite poor since it has 3 fixed operations regardless of the size of n.

When determining the Big O of a solution we don’t need to count every single operation of a function, we need to think of the big picture. If we where to input 1,000,000,000 into both of the functions to stress their performance we’d recieve the following graph.

The first function based on a mathematical formula is represented in gray, regardless of the number we put in it stays fairly constant due to the fact that it only has to do 3 operations, and returns an answer in milliseconds.

However the second function which we all would have probably written returns an answer in more than 1.2 seconds (depends on your personal computer specs). But this is ocurs because our function now has to d0 5(1,000,000,000) +2.

An algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases. In other words

f(n) can be linear (f(n) = n)
f(n) can be quadratic (f(n) = n^2)
f(n) can be constant (f(n) = 1)
f(n) is totally different

Big O allows us to talk about the runtime of an algorithm as the input grows.

We can think of the Big O of the first function as O(1) since it has a constant number of operations and it is reflected in the runtime..

For the second function 5(1,000,000,000) +2, or other wise 5n +2 the number of operations depend on n. If we think about it 2 operations in comparison to 1,000,000,000 (n) is quite negliglable so we can remove it and visualize our operations as 5(1,000,000,000). However since the number of operations grow proportionally with n we can also disregard the 5, ending up with a O(n).

When simplifying your Big O constants don’t matter and we have to think about the big picture for example

O(n^2 + 5n + 8) = O(n^2)

If thinking about n = infinity 5(n) is meaningless in comparison to n² or infinity squared.

To help when analyzing Big O there are a few rules to help.

1. Arithmetic operations are constant
2. Variable assignments are constant
3. Accessing elements in an array (by index) or object (by key) is constant
4. In a loop the complexity is the length of the loop times the complexity of whatever happens in the loop (if we have a for loop with n and a nested for loop with n the Big O = O(n²) )

To end this article you can picture the perfomance of your code as

So far we have been talking about Time Complexity for Big O, Space Complexity also exists. But that’s something for another article…