Mastering Data Structures & Algorithms: Big O Notation (Part 1)

This is the first part of a blog post series on algorithms and data structures. This topic might sound a bit theoretical at first, but it will help you become a better developer by knowing different data structures and algorithms, their ups and downs, and how to write more efficient and scalable code.

In this series, we will cover various aspects of algorithms and data structures, such as sorting, searching, hashing, graphs, trees, and more. We will also learn how to analyze the performance of algorithms using asymptotic analysis. By the end of this series, you will have a solid foundation of algorithms and data structures that you can apply to any programming problem.

In this first part, we will focus on the analysis of algorithms. We will learn what asymptotic analysis is, how to use it to compare different algorithms, and what factors affect the running time and space requirements of an algorithm. Let’s get started!

Why can't I just compare two algorithms by measuring the time it needs to run?

One common mistake that beginners make is to compare the runtime of two different algorithms by simply running them on the same input and measuring the time elapsed. This approach is flawed for several reasons:

1. The runtime of an algorithm depends not only on the algorithm itself, but also on external factors such as the hardware, the programming language, the compiler, and many more. These factors can vary significantly from one environment to another and introduce noise and bias in the measurements.
2. The efficiency of an algorithm shouldn't be seen as a single number, but as a function that describes how the runtime changes as the input size grows. For example, an algorithm whose runtime complexity grows linearly may take 1 second for an input of size 10, but 10 seconds for an input of size 100. Another algorithm that grows quadratically may take 0.1 seconds for an input of size 10, but 100 seconds for an input of size 100. Comparing the runtime of these two algorithms for a single input size does not give us a complete picture of their performance.
3. The runtime of an algorithm may vary depending on the distribution and order of the input elements. For example, some sorting algorithms perform better on already sorted or nearly sorted inputs than on random or reversed inputs. Comparing the runtime of these algorithms for a single input type does not account for their worst-case or average-case behavior.

Therefore, a better approach to compare the efficiency of different algorithms is to use theoretical analysis rather than empirical testing. The theoretical analysis involves using mathematical tools and techniques to derive and prove general statements about the behavior and properties of algorithms. In this blog post, we will discuss what asymptotic notation is and how it can be used to help us, determine the time and space complexity of algorithms.

What is asymptotic notation?

The asymptotic notation allows us to express the growth rate of a function as it approaches infinity, ignoring constant factors and lower-order terms. For example, if f(n) = 3n^2 + 5n + 2, we can say that f(n) is O(n^2), meaning that f(n) grows at most as fast as n^2 as n becomes large. Similarly, we can say that f(n) is Ω(n^2), meaning that f(n) grows at least as fast as n^2 as n becomes large. We can also say that f(n) is Θ(n^2), meaning that f(n) grows exactly as fast as n^2 as n becomes large.

In the diagram below you can see the different Greek symbols used in asymptotic notation, what they express, and how they relate to each other:

Using asymptotic notation, we can compare the efficiency of different algorithms by comparing their time and space complexity functions. For example, we can say that an algorithm that runs in O(n log n) time is more efficient than an algorithm that runs in O(n^2) time because n log n grows slower than n^2 as n becomes large. Similarly, we can say that an algorithm that uses O(1) is more efficient than an algorithm that uses O(n), because 1 grows slower than n as n becomes large.

However, asymptotic notation is not always sufficient to compare the efficiency of different algorithms. Sometimes, two algorithms may have the same asymptotic complexity, but different constant factors or lower-order terms that affect their performance in practice. For example, two sorting algorithms may both run in O(n log n) time in the worst case, but one may have a smaller constant factor or a better average-case behavior than the other. In such cases, we may need to use more refined techniques such as big-O with constants or average-case analysis to compare the efficiency of different algorithms. We will not cover these techniques in this blog post, but if you're interested in learning more, there are many great resources online.

Common time complexities in Big O

In the previous, we've already covered some common asymptotic time complexities. There are mostly six major types of time (and space) complexities that we need to know in Big O:

• Constant: O(1)
• Logarithmic: O(log n)
• Linear: O(n)
• Log linear: O(n log n)
• Quadratic: O(n^2)
• Exponential: O(2^n)
• Factorial: O(n!)

In the following chart you can see those time complexities and their growth rates:

The lower the big O, the more efficient the algorithm. For example, an algorithm that takes constant time or space (O( 1)) is better than one that takes linear time or space (O(n)), which is better than one that takes quadratic time (O( n^2)), and so on. Some common scenarios where we encounter different big O are: accessing an element in an array (O(1)), searching a sorted array using binary search (O(log n)), looping through an array (O(n)), sorting an array (O(n log n)), comparing every element in an array to every other element (O(n^2)), and adding a loop for every element in an array (O( n!)).

Common space complexities in Big O

Now we've discussed what time complexity is and what the most common time complexities in Big O. Let's now talk about what space complexity is and what the most common space complexities are in Big O.

Space complexity is a measure of how much memory an algorithm or a program needs to run. It depends on the size and characteristics of the input data. For example, if an algorithm needs to store all the elements of an array in memory, its space complexity will be proportional to the length of the array. On the other hand, if an algorithm only needs a constant amount of memory regardless of the input size, its space complexity will be constant. Space complexity is important because it affects the performance and efficiency of the algorithm or program. Sometimes, we can trade space for time, meaning that we can use more memory to make the algorithm run faster. We can use asymptotic notation to express the space complexity of an algorithm. For example, we can say that an algorithm has a space complexity of O(n) in the worst case, meaning that it needs at most n units of memory for any input of size n.

Conclusion

In conclusion, comparing the efficiency of different algorithms is not a trivial task and requires careful theoretical analysis. We should avoid comparing the runtime of two different algorithms by simply running them on the same input and measuring the time elapsed. Instead, we should use asymptotic notation and other mathematical tools to derive learn about the properties of algorithms.