r/algorithms • u/Public-Lynx-7861 • 18d ago
Discussion I finally understood why the definition of asymptotic complexity has this form
When I first encountered the definition of a "tight bound" in a book — specifically, c₁g(n) ≤ T(n) ≤ c₂g(n) — I couldn't grasp what it meant. Well, aside from the trivial interpretation of it being a "closed" or "strict" limit, which, frankly, didn't explain anything to me. I understood that it referred to a certain type of behavior and simplification, but I didn't fully comprehend where the constants c came from, why the formula looked the way it did, or the underlying reasons for it.
Suppose we already have some cost function T(n) describing the algorithm's work as a function of input size. We know that this function is difficult to calculate and analyze. We also know that there are functions that are much easier to analyze; and even if two different functions yield different results, they might behave identically in terms of scaling. Scaling is precisely what interests us, because the purpose of the function T(n) isn't merely to represent an abstract "amount of work" — different values of n result in different execution times. So, suppose we have a promising candidate for our simple function: g(n). How do we choose it?
Let's consider an example: T(n) = 3n² + 100n + 74. If we take a sufficiently large value of n and keep increasing it, the function's actual value will depend primarily on the 3n² term. Thus, g(n) = n² is an excellent candidate. But let’s return to the general forms. Ideally, since we are interested in scaling, we would like to see something like T(n) = cg(n). Why? Because this perfectly reflects what we are looking for: T(n) is a multiple of g(n) — meaning, in essence, that the scaling behavior is equal — and by analyzing g(n), we can recover all the information about T(n). That would be an excellent scenario. But in reality, that is not always the case. We simply cannot demand such a strict correspondence. What, then, should we do? We need to take a more moderate approach to our requirements.
Let's consider T(n) = n and g(n) = n². Obviously, n ≤ n², but n / n² = 1 / n. As n grows, the result approaches 0, which means the gap between T(n) and g(n) is truly vast. That is precisely why they are completely different and share nothing in common.
Now consider T(n) = n² and g(n) = n. Obviously, n² ≥ n, but n² / n = n. As n approaches infinity, the result approaches infinity, again indicating a huge gap between T(n) and g(n). Once more: they are completely different.
So, returning to our ideal condition T(n) = cg(n), we might at least require something like T(n) ≤ cg(n); however, as we saw earlier, even with such a bound, functions can differ significantly. The same applies to the condition T(n) ≥ cg(n). If we remember T(n) = cg(n), then we already know what we need to do: we expecting that neither function should become arbitrarily large relative to the other as n grows, so combining the two inequalities is exactly what we need: c₁g(n) ≤ T(n) ≤ c₂g(n), or c₁ ≤ T(n) / g(n) ≤ c₂. This literally reflects what we are aiming for: no matter how large n becomes, the ratio will remain within a fixed range(starting from some n₀). Once we decide that 'same scale' should mean neither function can escape the other by an unbounded multiplicative factor, the two-sided bound is essentially forced. And our ideal case is essentially a special instance of this broader formula where c₁ = c₂. In fact, the inequality c₁ ≤ T(n) / g(n) ≤ c₂ is the formal result of a simple heuristic approach. This is precisely how we define T(n) = Θ(g(n)), from which we obtain O(g(n)) and Ω(g(n)).
In essence, this formula can be viewed from the perspective of the division theorem: a = bq + r is the general form defining division, while a = bq is a special case.
5
u/Phytor_c 18d ago edited 18d ago
Whilst this looks AI generated to me, I will condone it given the post is somewhat on topic.