# Complexity of Problems and Ease of Verification

Comparison-based sorting algorithms have a minimum worst-case complexity of $$O(n \log n)$$, while it is easy to check that an array is sorted in $$O(n)$$ time.

Are there other problems with proven minimum complexity $$O(n^k)$$ for some $$k > 1$$ that can be checked in $$O(n)$$ time? How high can $$k$$ get?

• "Are there other problems with proven minimum complexity $O(n^k)$ for some $k > 1$ that can be checked in $O(n)$ time?" What do you mean, any other problems? $O(n \log n)$ is strictly less than $O(n^k)$ for any $k > 1$. Your comparison-based sorting example is not a proper example for your question. – orlp Oct 1 '18 at 13:29

Trivial arbitrarily hard example based on the existence of an one-way function $$f : \mathbb{N}^k \to \{0, 1\}$$. The problem:
Given a set $$S$$ of size $$n$$, can we choose a tuple $$t$$ formed from $$k$$ elements of $$S$$ such that $$f(t) = 1$$?
Since $$f$$ is one-way you must check all $$n^k$$ possible $$k$$-tuplets of elements from $$S$$, but checking whether a proposed solution is correct is simply $$O(1)$$ time.