Computer Science with Python — Time Complexity and Big O
Introduction to Computer Science Concepts
Many aspiring developers tend to jump straight into learning programming languages without getting a good grasp of the fundamental concepts of Computer Science. However, as they progress in their careers, they eventually realize the importance of understanding how a computer actually operates. That’s why I am starting a series on data structures and algorithms specifically tailored to Python programming.
When writing code, programmers always aim for optimal performance. There are usually multiple ways to solve a problem, but some solutions are much faster than others. To determine which solution is the most efficient, Computer Science employs the concept of Big O. This article will shed light on why it’s important to compare codes and how to interpret the Big O notation.
Time Complexity
When measuring an algorithm’s computational time, we use time complexity. To be specific, we use Big O Notation to describe the time complexity of an algorithm.
There are various ways to measure time complexity depending on the scenario. We have the worst case, which is when the code takes the maximum possible time to run. The average case falls somewhere in the middle, while the best case is the minimum time taken by the algorithm. We use Greek letters to describe different scenarios.
- Ω (Omega), best case, which solves a problem for the best input. However, this may only apply to a single example of an algorithm, while other cases may take more time.
- The average case is represented by θ (Theta). When we run the same algorithm on different inputs, we can determine how long it takes to complete the computations.
- The longest time to complete the algorithm is represented by Ο (Omicron), which is what we refer to as Big O. This is the most common case used to describe time complexity, and we will be discussing it in this article.
O(1), O(n) — Constant and Linear Time
The simplest option is to use O(n) notation, which means that the running time of the algorithm increases proportionally with the size of the input data. This is ideal when the algorithm needs to examine all values. In Python, this can be easily achieved through a loop.
def linear_o(n):
for i in range(n):
print(i)The most efficient variant of Big O is O(1). If you can make your algorithm work in this way, it will be the most optimal solution. An example of such an algorithm is a basic addition of numbers. Regardless of how large the number n is, the number of steps needed to get the result remains the same, which is just one step.
def add(n):
return n + nOne crucial idea to understand is the concept of the drop constant. Simply put, this means that we don’t include constant numbers in the O(n) notation. For instance, if we have an algorithm that executes two identical functions, it would be considered as running at O(2n). However, we would drop the 2 and only write it as O(n). The given example is an instance of such an algorithm.
def two_identical(n):
for i in range(n):
print(i)
for j in range(n):
print(j)O(n²) — Quadratic Time
It’s important to understand the concept of O(n²). When a second loop is added inside the first one, it doesn’t simply run twice. Instead, it runs n * n times. This algorithm is less efficient compared to the previous examples. As the input size increases, the number of steps increases exponentially. For instance, if the input is 5, it takes 25 steps, but for an input of 10 (which is twice as much), it takes 100 steps (four times as much). It’s advisable to avoid this type of algorithm for large inputs as it takes an enormous amount of time.
def o_squeared(n):
for i in range(n):
for j in range(n):
print(i, j)We can go even further and add another small loop after the first one finishes. In this case, our algorithm runs even longer, but the degree of the power won’t change — O(n²+n). According to the drop non-dominants concept, we don’t take into account the smaller degree and remain just O(n²).
def o_squeared(n):
for i in range(n):
for j in range(n):
print(i, j)
for k in range(n):
print(k)O(log n) — Logarithmic Time
One of the fastest types of algorithm has a time complexity of O(log n). In computer science, it is usually described by the binary search algorithm. Essentially, when searching for some sorted item in a list, we can divide it into two parts and understand, in which part to search at the next step. As a result, we don’t need to look into each element of the list (which is O(n)) but can make it way faster.
To gain a basic understanding, let’s visualize how various algorithms search for the number 29. O(log(n)) completes this task much faster. However, it’s important to note that there isn’t a single algorithm for all programming tasks, and it’s crucial to understand the differences.
It’s also worth mentioning the O(n log n) type. It is used by some sorting algorithms and it is the best way to sort a list. Still, the main types are as we have previously described: O(1), O(n log n), O(n), and O(n²).
When comparing different types of complexities, we typically plot them on the same graph. While we haven’t covered all of them here, this gives us a general understanding of how different algorithms compare in terms of effectiveness. Ideally, we want to avoid the bad areas of the plot and aim for the fair or good zones, but this can be challenging in practice. To achieve this, it’s important to have knowledge of standard data structures and algorithms, which we will discuss in future articles.
Conclusions
This article explores computer science and algorithms, specifically the Big O Notation. When comparing algorithms, we measure their worst case using the O notation. There are several common types of Big O, but we’ll cover the four main ones:
- O(n²) — a slow option involving a loop within a loop. Also called quadratic time.
- O(n) — proportional and standard, linear time.
- O(log n) — a great way to optimize an algorithm through division. This is called logarithmic time.
- O(1) — the fastest and most ideal type, or just constant time.
In future articles, we’ll delve into specific data structures and algorithms. This knowledge is valuable for creating data pipelines and other Python tasks.
I can be found on Linkedin and I am looking forward to connecting with you. Let’s engage in discussions about the intricate world of data science and data engineering.
