Big-O explained simply

Big-O notation is a tool used to describe the efficiency of a program, specifically how the amount of work increases as the input size grows. To illustrate, consider three examples of functions that process lists of items.

The first example, `first(items: list[Any]) -> Any`, returns the first item in a list regardless of its length, performing only one step. This function has a Big-O of O(1) or constant time, since the work doesn't change with the size of the list.

The second example, `count(items: list[Any]) -> int`, computes the number of items in the list by iterating through each one and incrementing a counter. As the list grows, the number of steps increases linearly with the input size, resulting in a Big-O of O(n), or linear time.

The third example demonstrates a more efficient search technique. Given a sorted phonebook, we can locate a name by repeatedly dividing the remaining portion of the list in half, similar to how binary search works. This halving process yields a Big-O of O(log n), where the work grows very slowly as the input size increases. For instance, a phonebook of a billion names would only require about 30 steps to find a name using this method.

When comparing these three scenarios, it becomes apparent that Big-O notation has practical implications in real-world programming. Let's examine two versions of a function that checks for duplicates within a list. The first version, `has_duplicates_v1(items: list[Any]) -> bool`, employs a list, `already_seen`, to keep track of previously encountered elements. It checks if an item exists in this list by scanning the entire `already_seen` list, resulting in an O(n²) Big-O complexity.

The second version, `has_duplicates_v2(items: list[Any]) -> bool`, utilizes a set, `already_seen`, to store the encountered elements. The key advantage of using a set is that checking for the presence of an item is an O(1) constant-time operation. Consequently, the Big-O of this version is O(n), which is significantly more efficient than the list-based approach.

In fact, when tested on a list of 20,000 items, the set-based function completed in approximately 0.001 seconds, while the list-based version took around 1.1 seconds - a thousand times faster.

In summary, understanding Big-O notation can help developers optimize their code and improve its performance, especially when dealing with larger datasets. Choosing the appropriate data structures, such as switching from a list to a set, can make a substantial difference in the efficiency of a program.