1
$\begingroup$

I wanted to understand how to establish both the lower $\Omega$ and upper bound $O$ on an algorithm to conclude it runs in $\Theta$ (note that I am not trying to prove that the algorithm is the most optimal and that no better algorithm exists).

To establish a $O$ I thought that one just has to prove somehow that the algorithm will never take more than $f(n)$ (for sufficiently large inputs) for alll possible input to the algorithm $A$. I think that should establish an upper bound in the worst-case, right? (since we are considering an upper bound for all inputs, it satisfies the worst-case scenario because it considers every single input).

But to establish a $\Omega$ in worst-case we need to argue that it will take at least $f(n)$ for some family of inputs (of size $n$). Is this correct?

My reasoning: In worst-case analysis we care about the performance of our algorithm in the worst-case. So to establish a $\Omega$ we need to show that there is exists some input (i.e. one that makes the specific algorithm perform the slowest) that could be given to use adversarial (that is why we need the quantifier exists rather than for all). So if there is some input that makes $A$ run in $f(n)$ in the worst case, an adversary could give us that input every time so we always run in $f(n)$. So we only need one to exists. But if we show we can never run in more than $f(n)$ then that input is really the "worst-case" because there cannot be any input that makes us run is more than $f(n)$. Is that sort of right? Basically, there exists guarantees worst case lower bound since an adversary could always give us that input and the for all guarantees a upper bound on any other potentially "worst" input.

$\endgroup$
  • $\begingroup$ No, $\Omega$ relates to the worst-case as well, so you'd need to use the same class of inputs for $O$ and $\Omega$ in order to get a $\Theta$. $\endgroup$ – Raphael Feb 10 '16 at 12:53
  • 1
    $\begingroup$ @Raphael I disagree. The only way you can be sure that what you think is the worst case really is the worst case is by proving an upper bound on all inputs. $\endgroup$ – Yuval Filmus Feb 10 '16 at 20:22
  • $\begingroup$ @YuvalFilmus But we never do that for Landau worst-case bounds! We take some class, analyse the algorithm on it, and argue (more or less formally) that there is no class with worst $\Theta$-performance. Only very rarely do we find and rigorously prove an absolte worst-case. $\endgroup$ – Raphael Feb 11 '16 at 11:58
  • $\begingroup$ @Raphael That's right, we're only interested in the worst case up to a constant in the running time. Otherwise, this is precisely the usual way we analyze algorithms. $\endgroup$ – Yuval Filmus Feb 11 '16 at 12:53
0
$\begingroup$

Your observations are correct for the worst-case time complexity, which is the most common measure of time complexity, other than a small point – usually we prove an upper bound of $Cf(n)$ and a lower bound of $cf(n)$, where the constants $c,C$ need not match (and usually aren't explicit, being instead hidden in asymptotic notation).

There is a subtlety here – as you correctly mention, formally speaking we need a hard instance for every $n$. Usually this is not a problem since instances can be "padded" – if we have a construction that only works directly for even $n$, perhaps we can pad it to get a construction that also works for odd $n$. But in computational complexity we are sometimes considering more general and abstract cases in which this is not the case, and the only guarantee is that the running time is $f(n)$ for infinitely many $n$. We denote this by $\Omega^\infty(f(n))$ or $\Omega_\infty(f(n))$. This is the negation of $o(f(n))$, that is, all we can conclude if $o(f(n))$ doesn't hold.

$\endgroup$
  • $\begingroup$ I think you are missing the biggest misunderstanding in the question: $\Omega$ is not "some-case", it's also worst-case. I'm not completely sure what happens if you show $O$ w.r.t. one and $\Omega$ w.r.t. another class; when showing $\Theta$-bounds, I'd stick to using the same class if possible at all. $\endgroup$ – Raphael Feb 10 '16 at 12:54
  • $\begingroup$ I strongly disagree, as I explain in my comment to the post itself. $\endgroup$ – Yuval Filmus Feb 10 '16 at 20:23

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