1.2.3. Asymptotic Complexity

So, we will start with asymptotic complexity, which is the way of measuring the efficiency of algorithms and writing down this measure in a way that we can compare easily across algorithms.

Asymptotic complexity is a method used in computer science to estimate the efficiency of algorithms, especially when dealing with large inputs. We measure how the performance (like time or space) of an algorithm changes as the size of the input data grows. This measurement allows us to compare different algorithms based solely on their performance for large datasets, without worrying about the specifics of their implementation.

Imagine you're comparing two delivery services for a growing online store. One service charges a flat fee and takes a fixed amount of time, while another service varies its price and delivery time depending on the size of the shipment. If you were to analyze their performance, you'd want to see how they stack up as your shipment sizes increase. Asymptotic complexity helps you do something similar with algorithms, by allowing you to see which service is more efficient as your needs grow.

We need a notation to compare two different algorithms, which operates on the same types of inputs and produce the same type of outputs.

To effectively communicate the efficiency of algorithms, we use specific notations. The most common is Big O notation. This notation describes the upper bound of the run time of an algorithm, providing a way to compare relative efficiency between algorithms by focusing on the most significant factors affecting their performance as inputs increase.

Think of it like comparing cars based on their top speeds instead of their performance under specific conditions. For example, two cars might perform differently in city traffic, but if you only cared about speed on the highway (the worst-case scenario), the car with the highest top speed (Big O) would be the better overall choice for driving long distances.

Asymptotic complexity measures the running time of an algorithm as inputs grow larger and larger as the function of the inputs.

Growth rates illustrate how the running time or space of an algorithm increases as the input size increases. Different algorithms may have different growth rates, which will tell us how one algorithm outperforms another as the size of the data grows. For example, an algorithm that runs in linear time will generally perform better than one that runs in quadratic time as the input size becomes very large.

Consider planting trees in a garden. If you plant trees at a constant rate (linear growth), every year you will have a predictable increase in the number of trees. However, if your growth involves a massive expansion where every tree you plant leads to twice as many planting in the following year (exponential growth), you will quickly overwhelm your garden space. Asymptotic complexity helps us understand these differences as data sets grow.

We will develop some notation, typically the big O notation in order to smoothen out some of the complexities of algorithms and group them into large chunks, which are equivalent.

By using notations such as Big O, we can simplify the comparison between algorithms and categorize them based on efficiency. This categorization helps in deciding which algorithm to implement based on the expected data sizes and performance demands, effectively allowing developers to make informed choices without getting bogged down in implementation specifics.

This is akin to categorizing fruits by size: if you know whether a fruit is small (like a grape) or large (like a watermelon), you can quickly estimate how many fit into a basket without measuring each fruit individually. In algorithm analysis, using Big O allows you to estimate performance among different algorithms without having to run each one on every conceivable input size.

--