# In algorithm analysis what does it mean for bounds to be "tight"

For example we could say alg(x) runs big omega(n) but this bound is not "tight".

What is meant by "tight"? Is it that the bound isn't at its maximum?

So maybe a tighter bound could be big omega (1)??

• Do you know what I mean if I say "$f(n) \leq 77n$ but this bound is not tight"?
– Raphael
Apr 16, 2017 at 10:48

Generally speaking, a bound is tight if there is no "better" bound.

Take, for instance, $f(n) = \sin(n)$. Then, $-1.5 \leq f(n) \leq 2n$ are valid bounds on $f$ but they are not tight -- there are better bounds, e.g. $-1.2 \leq f(n) \leq 1.5n$.

Now, $-1 \leq f(n) \leq 1$ are tight bounds -- there are no tighter ones.

You will note that the range of $n$ is relevant here. I implicitly let $n \in \mathbb{N}$ (or $\mathbb{R}$ if you want) here; if we consider $n \in \{ \pi i \mid i \in \mathbb{N} \}$ there are better bounds.

Now, using Landau symbols the terminology is used similarly: $f \in \Omega(n)$ is a tight bound if there is no "better" $\Omega$-bound, i.e. one with a faster-growing parameter function. If we also know that $f \in O(n)$, then both bounds are tight and we have $f \in \Theta(n)$. It is, however, very possible that you have, say, $f \in \Omega(n)$ and $f \in O(n^2)$ and both bounds are tight.

Here, and in particular in the context of algorithm analysis, the range of (the implicit) parameters is relevant as well: are you talking about all inputs? Worst-case inputs? The average case? For instance, $\Omega(n)$ is a tight (lower) bound on the asymptotic running time of (improved) Bubblesort if you consider the best case, but not for average or worst case.

Note that "tight" can be relative to your goals. If you want to prove asymptotics of the form $f \sim g$, you wouldn't call a $\Theta$-bound "tight".

This definition from Wikipedia makes it simpler:

Tight bounds An upper bound is said to be a tight upper bound, a least upper bound, or a supremum, if no smaller value is an upper bound. Similarly, a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum, if no greater value is a lower bound.

https://en.wikipedia.org/wiki/Upper_and_lower_bounds#Tight_bounds

This question might be a duplicate of this question.

$O$ notation represents the upper bound of an algorithm and $\Omega$ the lower bound. $\it{\Theta}$ combines the two yielding an asymptotically tight bound.

• what exactly does "tight" mean though. And must we always use theta when refrencing it? Apr 16, 2017 at 4:04
• Think of an algorithm that has running time $T(n) = 3n^2 + 4$. There are multiple bounds that apply above or below, but only $\Theta(n^2)$ binds it both above and below. The technical definition for $f(n) = \Theta(g(n))$ is that for any integer $N_0$ there are two constants $c_1, c_2$ so that when $n > N_0$, $c_1g(n) \leq f(n) \leq c_2g(n)$. Apr 16, 2017 at 4:09
• While true, your post fails to answer the question. Explaining "tight" using $\Theta$ is like explaining flour by showing people a cake.
– Raphael
Apr 16, 2017 at 11:00
• I see. I'll keep that in mind next time I try to answer something. Thanks for the feedback. Apr 16, 2017 at 11:14