Java programmer expert
Big O notation: analysis of algorithms’ time and space complexity
Since the early days of information technology, developers have been striving to write code that not only works but also efficiently utilizes hardware. In the past, when processors were expensive and slow, and memory was scarce, optimization was crucial, with literally every machine instruction mattering. Similarly, when working with large data sets, algorithms had to be very sophisticated because computational time was heavily limited.
Hence the need to compare the efficiency of algorithms, and this is where Big O notation plays an important role. In this article, we take a closer look at the analysis of algorithmic complexity using Big O notation.
Big O notation meaning
Big O notation is a mathematical notation in computer science that is used to describe the asymptotic complexity of algorithms, that is, it describes the worst-case scenario (upper bound) of an algorithm based on the size of the input data. In other words, this notation helps us understand how the efficiency of an algorithm changes depending on the amount of data being processed.
A short history of Big O notation
Its theoretical foundations were laid in the early twentieth century when people did not even dream of computer algorithms. However, it was not until the 1960s that Big O notation became popular and widely used in computer science, mainly thanks to pioneers such as Donald Knuth. Knuth detailed and popularized the use of this notation in his well-known work The Art of Computer Programming, first published in 1968. Knuth’s work contributed significantly to the standardization and widespread use of Big O notation in the analysis of algorithms and computer programs.
How is Big O notation used?
Big O notation is used to theoretically compare the efficiency of different algorithms. For example, when deciding which sorting algorithm is more appropriate to use in a given situation, we look at the notation for the different algorithms.
It also helps us predict how an algorithm will behave with increasing amounts of input data. This knowledge is a prerequisite for optimizing the algorithm and using resources more efficiently.
When solving complex problems, knowing the complexity of the Big O of different algorithms can lead to the selection of appropriate data structures and algorithms. This helps us to design efficient solutions to real-world problems.
Big O notation is used in analyzing both time complexity (how runtime grows with input size) and space complexity (how memory usage grows with input size).
Big O notation explained
In Big O notation, O represents the order of the function, and f(n) represents a function describing the time complexity of the algorithm with respect to the input size n. The notation O(f(n)) means that the time complexity of the algorithm does not grow faster than a given function with input n. The mathematical function f(n) thus describes how the running time of the algorithm increases as the input size increases. For example, O(n) notation means that the execution time of the algorithm grows linearly with the input size.
Big O notation examples
We now show the most common types of complexity, how they are written in Big o notation, and an example of an algorithm with a given complexity in a clear table.
| Big O notation | Complexity | Algorithm example |
| O(1) | Constant | Access an element in an array using an index |
| O(log n) | Logarithmic | Binary search in a sorted array |
| O(n) | Linear | Linear search in unsorted array |
| O(n log n) | Linearithmic | Efficient sorts like MergeSort |
| O(n²) | Quadratic | Nested loops iterating over input |
| O(2n) | Exponential | Brute-force algorithms testing all combinations |
| O(n!) | Factorial | Algorithm generating all permutations of a set |
Big O notation rules
When using Big O notation, there are some basic rules that help to express the asymptotic complexity of algorithms accurately and consistently. Big O notation can be used for both time and space complexity.
Ignoring lower orders
When determining the Big O notation, only the highest order is considered. Lower orders and constants are ignored because their influence becomes negligible for large inputs.
Fo example, if an algorithm has a time complexity f(n) = 3n² + 5n + 82, the complexity is O(n²) because n² is the highest order.
Ignoring constants
The constants are ignored, because they do not have a significant effect on the growth function for large input values.
Example: If the algorithm has a time complexity f(n) = 2n, the complexity is O(n).
Sum rule
If the algorithm consists of several steps that are executed sequentially, the total complexity is determined by the highest order between the steps.
Example: If an algorithm has two parts with complexity O(n) and O(n²), the total complexity is O(n²).
Product rule
If the algorithm contains nested cycles, the total complexity is the product of the complexities of the individual cycles.
Example: If the outer cycle has complexity O(n) and the inner cycle also has complexity O(n), then the total complexity is O(n * n) = O(n²).
Logarithms
Logarithmic functions grow more slowly than polynomial functions, so in practice they are often negligible compared to polynomials.
Big O notation programming practice
If we have implemented an algorithm and want to find out its complexity without analyzing the time complexity of individual code blocks, we can run the algorithm sequentially for input data 1 to N and measure the run time of the routine. From these measured values, we can then construct a graph in Excel of the dependence of the input data (x-axis) on the run time of the algorithm (y-axis). From the shape of the curve, we can then roughly estimate the complexity of the algorithm and, depending on the type of algorithm, see if there is room for optimization.
