The term lower bound comes from math and applies to more than just complexity theory. What we see is that such and such is "a" lower bound. In complexity theory should this not be phrased as "the" lower bound, or better still the lowest bound. I can see where lower is a relative term, but the complexity of a given problem would seem to have exactly one minimum. Am I being overly semantic here? what I would like to say is that the lower (or lowest) bound on the complexity of SLL(k) testing is exponential.


  • $\begingroup$ What's wrong with Big-$\Omega$ $\endgroup$ – m1cky22 Aug 4 '16 at 15:54
  • $\begingroup$ Lower bounds are not minima. I think you have something muddled. $\endgroup$ – Raphael Aug 4 '16 at 18:08

If you want to talk about the complexity of a problem, just use "the complexity of the problem" and don't bring lower bounds into it.

GOOD: "The complexity of SLL(k) testing is exponential."

GOOD: "The complexity of SLL(k) testing is at least exponential."

GOOD: "There is an exponential lower bound on the complexity of SLL(k) testing."

GOOD: "The complexity of SLL(k) testing is in $\Omega(2^n)$."

BAD: "The lower bound of SLL(k) is exponential." <--- Don't say this! There's more than one valid lower bound.

BAD: ""The complexity is at least $O(2^n)$." <--- Don't say this! Big-O is an upper bound; it doesn't go with "at least".

  • $\begingroup$ I like the idea of just leaving the confusing to me lower bound term out altogether, as long as it is clear that I am saying that something cannot be done in less than exponential time. $\endgroup$ – slkpg Aug 5 '16 at 12:39

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.