2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Derek Elkins left SE Jan 8 '18 at 1:08
  • $\begingroup$ @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. $\endgroup$ – Paradox Jan 8 '18 at 1:13
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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