Imagine you are a talented chef in a bustling restaurant. Every evening, you prepare delicious dishes to satisfy the hungry taste buds of your customers. However, you start noticing that as the number of orders increases, your cooking process takes longer and longer. You wonder how to measure and explain this increase in execution time. That’s where Big O notation comes into play.
In the world of computer science, efficiency is essential. In this article, we will break down Big O notation.
First of all… What is Big O?
Big O notation is a way to describe the efficiency or time complexity of an algorithm. It helps us understand how the performance of an algorithm scales with the size of the input. Essentially, it tells us how fast an algorithm executes relative to the size of the problem it solves.
Enough talking, our time is running out.
First of all the common Big O notations and what they mean:
- O(1) — Constant time complexity:
The algorithm’s execution time remains constant regardless of the input size. It means that the algorithm takes the same amount of time to complete, regardless of how many elements are involved.
Imagine you have a box of toys and you want to find a specific toy, like a dolls. It doesn’t matter how many toys are in the box, if you know exactly where the dolls is, you can find it in one go. It’s like knowing the exact location of the toy you’re looking for. Regardless of the other toys in the box, you know exactly where to find the right one.
2. O(log n) — Logarithmic time complexity:
This time complexity is often seen in algorithms that divide the input in half at each step. It means that as the input size increases, the number of operations required grows logarithmically.
Suppose you have a book of stories with 100 pages and you want to find a specific page. Instead of flipping through the book page by page, you can use a special method called “algorithme de trie”. You start by opening the book at the halfway point (page 50) and check if the desired page is before or after that page. By using this method, you can quickly narrow down to the desired page. For example, after checking page 50, you may realize that the page you’re looking for is before it, so you open the book at the halfway point of the first half (page 25), and so on. Each step brings you closer to the desired page, but you only look at a fraction of the book each time.
3. O(n) — Linear time complexity:
Linear time complexity implies that the execution time of the algorithm scales linearly with the input size. In other words, if you have n elements, the algorithm will perform a constant amount of operations for each element.
Suppose you have a bag filled with 10 crayons of different colors, and you need to find a red crayon. The only way to find it is to look at each crayon one by one until you find the red crayon. If you have 10 crayons in the bag, you will have to check all of them to find the right one.
4. O(n²) — Quadratic time complexity:
Quadratic time complexity indicates that the algorithm’s execution time grows quadratically with the input size. It means that for each element in the input, you need to perform an operation with every other element.
Suppose you have a 10x10 grid with colored cells. Now, you need to check each pair of cells to see if they have the same color. You start with the first cell and compare its color with the other 99 cells. Then, you move to the second cell and compare it with the other 98 cells, and so on. You have to perform 100 comparisons for each cell. In total, you will have to perform 100 * 100 = 10,000 comparisons to check all pairs of cells.
Now you have a idea of the 4 Time complexity. The next step will be ‘How to to calculate the Big O notation of a piece of code ?”
First, here are the key points to consider to help you:
1. Identify parts of the code that repeat or iterate, such as loops or repetitive function calls.
2. Determine the size of the input for your algorithm, i.e., the number of elements on which you perform operations.
3. Analyze how these parts of the code scale with the input size. Ask yourself how many times these parts are executed or how many operations are performed based on the input size.
Let’s see a big example:
Imagine you’re working on an e-commerce platform and need to calculate the total price of a customer’s shopping cart. You have a list of items, each with its own price, and you need to go through the list and add up the prices.
This is an example of linear time complexity, denoted as O(n), where n is the number of items in the list.
def calculate_total_price(prices):
total_price = 0.0
for price in prices:
total_price += price
return total_price
prices = [10.99, 5.99, 3.49, 8.99, 2.99]
total = calculate_total_price(prices)
print("Total price: $", total)Now, let’s see how we can apply the three points mentioned earlier:
1. Identify parts of the code that repeat or iterate:
In this Python example, the repeating part of the code is the `for` loop that iterates over each price in the `prices` list and adds it to the `total_price` variable.
2. Determine the size of the input for your algorithm:
The size of the input is determined by the number of items in the `prices` list. In this case, it represents the number of elements on which we perform the sum.
3. Analyze how these parts of the code scale with the input size:
The `for` loop iterates once for each element in the `prices` list, so the number of iterations is directly proportional to the size of the list. As the size of the list (number of items in the shopping cart) increases, the number of iterations and operations performed by the loop also increases linearly.
In terms of Big O notation, we can conclude that the time complexity of this code example is O(n), where n is the number of items in the `prices` vector. This means that the time required to calculate the total price increases linearly with the number of items in the shopping cart.
The subject of Big O notation can be complex, and it’s easy to overlook its practical application and relevance. Through this article, I hope you’ll realize that it’s more than just a calculation — it’s a mindset to adopt.
My work here is done now, as our time is limited.
See you soon!
