# Proving worst-case running time is in $\Omega(n^2)$

I was given the following method to argue that an algorithm $A$ has a worst-case running time of $\Omega(n^2)$:

We need to argue that there exists an input $x$ of size $n$, the running time of $A$ with input $x$, i.e., $t(x)$, is at least $cn^2$, where $x>0$ is a constant.

If you find a single input of size $n$ that gives A a running time of exactly, $n^2$, then couldn't there still exist a different one that is less than $n^2$, since we're only specifying one input and not all inputs? I'm having difficulty understanding the logic.

• Presumably you need to do this for each $n$. There could be only a single input $x$ for each $n$ that takes $cn^2$ time and that would suffice because you are looking for the worst-case running time. Jan 8, 2018 at 1:08
• @Derek Oh, so since it's worst-case, it doesn't matter if there are other inputs that give a faster run-time. Only finding one ensures that it won't grow at a rate slower than that input. Jan 8, 2018 at 1:13

The worst-case running time of an algorithm $A$ is a function $T(n)$ which accepts an input length and outputs the maximum running time of algorithm $A$ on an input of length $n$:
$$T(n) = \max_{|x|=n} \mathrm{runtime}(A,x).$$
Therefore to prove that $T(n) \geq S(n)$, it suffices to show that for each $n$ there is an input $x_n$ of size $n$ such that $\mathrm{runtime}(A,x_n) \geq S(n)$. The fact that there exist other inputs on which $A$ performs better is completely immaterial, since the worst-case running time depends on the worst input.