Proving that an algorithm $A$ runs in $\Theta(f(n))$ time in the worst-case [duplicate]

Question

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.

Answer 1

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.