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)??

  • $\begingroup$ Do you know what I mean if I say "$f(n) \leq 77n$ but this bound is not tight"? $\endgroup$ – Raphael Apr 16 '17 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".

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ what exactly does "tight" mean though. And must we always use theta when refrencing it? $\endgroup$ – 78lee Apr 16 '17 at 4:04
  • $\begingroup$ 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)$. $\endgroup$ – Christopher Bell II Apr 16 '17 at 4:09
  • 2
    $\begingroup$ While true, your post fails to answer the question. Explaining "tight" using $\Theta$ is like explaining flour by showing people a cake. $\endgroup$ – Raphael Apr 16 '17 at 11:00
  • 1
    $\begingroup$ I see. I'll keep that in mind next time I try to answer something. Thanks for the feedback. $\endgroup$ – Christopher Bell II Apr 16 '17 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.