Article 2 of learning DSA in Python.

Big - O Notation

To people who are wondering, why should we learn about big O notation before learning DSA, the reason is, DSA deals with problems which can be time consuming and space consuming.

A terribly executed code may waste these resources which in real-time costs a lot. Hence, Big-O notation.

Types of Notations

There are primarily three types of notations :-

• Omega (Ω) :- Best Case

• Theta (θ) :- Average Case

• Big-O (O) :- Worst Case

We always consider the "Worst Case" while writing the code.

Here is a simple example about how we calculate time complexity:-

In the above example, we can see it's a basic "for" loop which runs for 5 iterations.

Since the loop iterates over 'n' times, we calculate the time complexity of this code as O(n).

Here is an another example :-

Here we can see two different sets of "for" loops, one loop which runs for 'n' times, in the second loop, it runs for 'n*n'.

In this example, n = 3

• For first loop, the loop runs for just 3 times, hence O(n)

• For second loop, the outer loop runs for 3 times and the inner loop runs 3 times for each iteration. So it can be calculated as 3+3+3 or in other words, 3*3. Hence, O(n²).

Here comes the tricky part, in the above example, we can see that there are two different sets of loops, so which loop to choose.

The rule of thumb is to always consider the bigger time complexity. So in this case, while choosing between O(n) and O(n²), we always write O(n²).

Now comes a different problem, what if there are three "for" loops?

It is an important rule to remember, we always drop constants.

To understand more about "dropping constants", let's have a look at the below example:-

As you can see, there are three O(n) loops. while writing the time complexity for this code, we don't write it as O(3n). The reason being :-

By adding constants, it doesn't affect the graphical representation of the time complexity, hence we drop the constants.

This is how Big-O notation works. Hope the explanation was clear and stay tuned for more updates.