This question already has an answer here:
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.