Big O Notation: Simply Explained

I suppose you already have some experience in coding and you’ve come to realize how super important it is to have a performing algorithm, particularly when the system you’re working on becomes huge, or you’re still a CS student and you have just started some class that often talks about complexity or Big O Notation, you may feel lost at first, but don’t worry, through this article, I’ll try to make it clear for you.

This article contains 2 parts and a bonus section. The first part will include some theory about the Big O Notation, so if you’re not much into theory, you can jump to the second part which explains how to calculate complexity. The bonus will show why Binary Search Algorithm is O(log n).

PS: There are other notations used to express complexity and Big O is the most commonly used.

Part 1 : What is Big O Notation?

The general definition that we usually come across is something like this: “Big O notation is used to express the time complexity of a given algorithm…”, or a simpler perception that we could have is that it is something related to meausring time execution of a given algorithm, but how exactly? It’s still vague! Let’s first talk a bit about Big O Notation in mathematics, because it is the same idea behind complexity. In mathematics, it is the most commonly used asymptotic notation to describe the behavior of a function when the argument tends towards a given value, generally a very large value. Formal expression,as defined here is as following:

Let f, g be real-valued functions (with domain R or N), and assume that g is positive. We say that f(x) is O(g(x)) if there are constants M and k so that:

|f(x)| <=M |g(x)| For every x>k .

We read this “f is big O of g” and it is often written as f(x)=O(g(x)). …(1)

One possibility among many, visually it would look something like:

Now let’s see how this is applied in time complexity:

Let n be the input size and f(n) is the worst case complexity, i.e the running time required by an algorithm to run given an input n. … (2)

Don’t worry if it’s still not clear yet, you’ll figure it all out in the example below :) :

Let a be an array of size n (input), and imagine n is very large, and let’s perform a linear search in this array. We want to find an element e in this array. So, we will iterate over the array until we find the element. The best-case scenario is that the element we’re looking for is at a[0], and that we access the array only once, and the worst-case scenario is that the element is at the last index, a[n-1], which means we need to iterate over the entire array until we’ve reached its limit, and we need to access the array n times to find element e, and that’s what Big O Notation is used for, to measure worse-case complexity. If we apply the rule stated in (2) to this example:

Given an input n (size of the array), and f(n) the worse case complexity, and based on (1) notation, we can say that:

Let g(n)=n (the number of times we access the array in the worst scenario).

f(n)=O(g(n)) , i.e f(n) = O(n).

this means in the worst case scenario, we need to perform n operations (accessing the array) to find our element e.

Great, now it should makes sense to you, doesn’t it?

This was just a simple example to make the theory clear, now let’s see how to calculate complexity in other examples.

Part 2: How to calculate Complexity?

It is calculated based on the number of computer instructions. Simple instructions like assignment, arithmetic, comparison, accessing array elements are constants of O(1), each one of them is considered as a single operation.

Eg:

x=1   //O(1)

If Then Else: we consider the complexity of the statement of the max instructions. Let’s take a look at the example below:

amount = 50          //1
If amount < 50 Then begin        //1
   status = “Amount insufficient”      //1
   End
Else begin
   status= “Amount accepted”        //1
   bonus = amonunt * 0.1           //1+1 = 2 (assignment+arithmetic)
End

The complexity of this code is: f(n) = 1 + 1 +max(1, 2 + 1) = 2 + 3 = 5

f(n) = 5, constant, and that means it is O(1).

-Loops (for,while,repeat): Complexity is the number of looping multiplied by the number of operations inside that loop.

-Nested loops: At least one loop inside of the main loop, so the complexity is at least O(n²).

Bonus: Why complexity is O(log n) in Binary Search Algorithm?

Among all the other common complexity values, O(log n) that wasn’t obvious to me at first sight, which is why I wanted to add it as a bonus to this article.

Before we find out why Binary Search Algorithm has O(log n), we first need to know the concept of this algorithm. The idea is that in a sorted array, we lookup an element by dividing the array by 2 in each iteration, we kind of play the guessing number game, for example, I ask you to pick a number between 12 and 50, and I started guessing which number you picked, let’s say 47 and then you tell me that it is between 12 and 40, and then I guess a number between 12 and 40, for instance, 30, and you tell me that it is between 12 and 30, and it goes this way, minimizing intervals until we find the guessed number. The idea is to keep dividing the array by 2 in each iteration until we find the element we’re looking for.

So if N was the size of the array, for the first iteration, we divide N/2, and in the second iteration, N/2*2, the third iteration, N/2*2*2, … if we’ll have x iterations, then N will be divided by 2^x, i.e N/2^x.

So, in the worst case scenario, the number of x will be large enough so that N/2^x = 1. Now, mathematically speaking:

N/2^x = 1 <==> N = 2^x , and now we can apply log2 since we have 2^x and N > 0:

<==> x = log(N)

And hence O(log n), it means the x iterations are run in a time of log(N).

Conclusion

In this article, we covered the theory behind the Big O Notation, how to calculate it, and showed complexity is O(log n) in Binary Search Algorithm. Big O Notation is used to express the worse-case complexity, there are other notations used for Best-case complexity, average-case complexity, etc. For more you can take a look at this link.

Finally, I hope you enjoyed this article, if you have any suggestions or feedback, I would love to see them in the comment section. Happy reading :)