Why Is My Code Slow? Big-O Explained With Real Timings

Many developers understand the concept of Big-O notation, which describes how the time complexity of an algorithm grows as the size of the input increases. However, few have witnessed the real-world impact of different Big-O complexities on their own machines. To illustrate this, the author conducted a simple experiment with a single problem: determining if any number in a list of numbers is repeated.

The author used three different methods to solve this problem and measured the performance on a standard x86-64 computer running Python 3.13. The methods were:

1. Nested loops: Comparing each item in the list with every other item

2. Sorting the list first, then checking adjacent items for duplicates

3. Using a set (a data structure that stores unique elements) to keep track of seen items

The author chose a difficult case: a list with no duplicates to ensure that each method had to process the entire list. The results showed a significant performance difference between the methods:

- With 1,000 items, nested loops took about 0.031 seconds, while the set method was around 0.00007 seconds

- At 10,000 items, nested loops took over 2 seconds, while the set method was just 0.0019 seconds (about 2,500 times slower)

- With 100,000 items, the set method finished in 0.024 seconds, while nested loops were skipped due to the long execution time

- At 1,000,000 items, the set method took 0.39 seconds, while the nested loops method was estimated to take around 6 hours (625 times slower)

The set method, which uses hashing to check for duplicates, has a time complexity of O(n), meaning its performance grows linearly with the size of the input. In contrast, the nested loops method has a time complexity of O(n²), leading to an exponentially increasing execution time as the input size grows. This dramatic difference highlights the importance of choosing the right algorithm based on the problem at hand and the expected input size.

The author learned three valuable lessons from this experiment:

1. Small test data can hide inefficient code. An algorithm that performs poorly on small inputs might still seem acceptable when tested on a limited dataset. However, this can lead to problems when the data grows, as demonstrated by the nested loops method.

2. Look for loops within loops when analyzing code complexity. Nested loops are often a sign of inefficiency, as they result in a quadratic time complexity (O(n²)). Identifying and optimizing these loops can lead to significant performance improvements.

3. Using data structures like sets or dictionaries can often provide a fast and efficient solution to common problems. These data structures offer constant-time (O(1)) lookups, making them ideal for tasks like checking for duplicates. In this case, the set method provided a substantial speedup compared to the nested loops approach, demonstrating the power of choosing the right data structure.

In conclusion, this experiment vividly illustrates the importance of understanding Big-O notation and how it impacts real-world performance. By recognizing the differences in time complexities and selecting appropriate algorithms and data structures, developers can avoid performance pitfalls and build more efficient software that scales well with growing input sizes.