What does it mean to say that \(f(n)\) is not in \(\mathrm{O}(g(n)) ?\)

At its heart, computational complexity is a theoretical estimation of the resources, such as time or memory, required by an algorithm to solve a problem as the size of the problem's input, usually denoted by \( n \), increases.
This concept is fundamental since it helps categorize algorithms based on their performance and scalability. As the input size grows, some algorithms may only require incrementally more time or space, while others might need exponentially more, which becomes impractical for large inputs.
Understanding computational complexity is essential for developers to ensure that the algorithms they choose won't become the bottleneck as the scale of data increases.

Algorithm Analysis is the process of interpreting and understanding the complexity of algorithms. This includes determining both the time complexity, related to how quickly an algorithm runs, and space complexity, which is concerned with how much memory an algorithm uses.

Why it Matters

By analyzing algorithms, developers can predict how algorithms will perform under various conditions. It’s similar to assessing the fuel efficiency and speed of different car models to determine which is most suitable for long-distance travel.
Through such analysis, developers can optimize algorithms to enhance performance, spot potential inefficiencies, and avoid pitfalls that could lead to performance issues as the input data grows.

The growth rate of an algorithm describes how its resource consumption, like execution time or memory usage, increases with the size of the input data. It's crucial to understand that the growth rate is not about the absolute time it takes to execute an algorithm, but rather how this time changes as inputs become larger.

Analogy

Imagine filling up containers of different shapes with water. A flat pan represents a linear growth rate since the water level rises evenly. A tall, narrow glass represents a logarithmic growth rate, slow to start but quickly rising. And a funnel-gone-wild, resembling exponential growth, has initially slow increases that become drastically steep over time.
This concept helps in selecting appropriate algorithms for a given task, especially when handling big data where growth rate has a pronounced impact.

When we talk about the upper bound in the context of algorithm analysis, particularly using Big O notation, we're referring to a theoretical limit on how slow an algorithm can get as the input size increases—and always from a certain point onwards, which is known as 'sufficiently large inputs.'

Upper Bound Illustration

Consider this a speed limit for the algorithm: just as vehicles on a road shouldn't go faster than the speed limit, an algorithm should not surpass its growth rate as determined by its upper bound for large inputs.
The upper limit isn't a precise prediction but rather a guarantee that a certain level of performance will not be exceeded, ensuring a controlled environment for algorithm execution—a key factor for long-term scalability when processing larger datasets.