0
$\begingroup$

I occasionally see these terms used and I'm not really sure what is meant by all of them. Is it possible for an asymptotic bound that is not Big $\Theta$ bound to be "tight"? What does it mean for bounds that are not Big $\Theta$ to be tight?

Is there a difference between a tight Big $O$ bound and a Big $\Theta$ bound?

$\endgroup$
  • $\begingroup$ @Discretelizard Since it's possible to add multiple questions, I think it's fair to say "this is a duplicate of the combination of those X questions". $\endgroup$ – Raphael Jan 25 '18 at 12:25
0
$\begingroup$

$O$ and $\Theta$ refer to different properties of some function. In a sense, we know more of a function when we can describe it with $\Theta$ than with $O$.

However, usage of $O$ or $\Theta$ doesn't imply tightness of a bound. You have some function $f(n)$ that is a bound which you could either describe with $f(n)\in O(g(n))$ or $f(n)\in \Theta(g(n))$, but whether the bound is tight depends on the actual bound $f$.

So, as a tight bound means simply that there is no 'better' bound for all cases, a tight asymptotic bound (either in $O$ or $\Theta$, or even $\Omega$), simply means that there is no better asymptotic description of a bound.

An example of a tight bound with only $O$ is the time complexity of finding an element in an unordered list of size $n$. This complexity is bounded by $O(n)$ and this is tight. The complexity is not $\Theta(n)$, as there are cases when we find the element without scanning the entire list. (The asymptotic complexity of the worst case is $\Theta(n)$, though)

For more reading on bounds with Landau ('big $O$') notation, see the reference question How does one know which notation of time complexity analysis to use? and its answers.

$\endgroup$

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