Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to know if the following proposition is correct or not?

For any integer k, there exists an problem P for which, the minimum possible time complexity of any solution algorithm is $\Omega(n^k)$

Please give me creditable sources such as journal papers, books, etc. about the solution of the above question.

UPDATE: By algorithm I mean standard algorithms as discussed in computational complexity. i.e. an algorithm that for any binary encoded input of size n which corresponds to a problem instance, outputs 0 or 1 (or true or false)


share|cite|improve this question
Well, that is easy to prove for algorithms - we can just write an alogorithm that stalls for that period of time. The harder question - is there a problem that can only be solved with an alogithm of that complexity - is probably what you really mean. – Thomas Andrews May 2 '13 at 19:16
Why do you need a proof from an outside source? This is simply $k$ nested loops, each iterating $n$ times. – apnorton May 2 '13 at 19:18
I corrected my question. That was not what I meant. – Shayan May 2 '13 at 19:26
up vote 3 down vote accepted

Alternatively, look for the Time Hierarchy Theorem:

share|cite|improve this answer
Brilliant answer! Thank you. I didn't expect to find the answer here. – Shayan May 2 '13 at 19:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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