# Computational Complexity of Algorithms

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)

Thanks

• 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