Is there a task, so that any algorithm solving this task can not run better than $\mathcal{O}(n)$?

Question

More generally my question is, whether for any $k$ there is a task (e.g. sorting a list of length $n$), s.t. any algorithm solving this task can not run better than $\mathcal{O}(n^k)$? Any idea/reference is appreciated.

Answer 1

Indeed. As a simple example, finding the maximum of a list cannot be performed in less then $O(n)$ in general conditions, since in order to find the maximum one must necessarily examine all the elements. This lower bound to the complexity is also a significant one, as there exists an algorithm that performs the task in such time (the obvious one).

Sorting also has a lower bound of $O(n)$, for the same reason, but it is not significant in general. It can be shown that, without specific assumptions on the number of elements that are to be sorted, the task cannot be performed in less than $O(n \log n)$. But, indeed, sorting also fits your definition.

As for the general statement, consider finding the maximum of a $k$-dimensional array; this cannot take less than $O(n^k)$, if no assumptions are made about the ordering of the elements.

Answer 2

Take matrix multiplication as an example: Multiplying two matrices of size $n\times n$ will always take at least $O(n^2)$ operations: Simply because there are $O(n^2)$ elements that need to be processed, see this explanation. This minimal complexity is a relatively basic concept, which can be found in most undergraduate books about algorithms.

For the particular problem of matrix multiplication, there is actually a lot of research about finding algorithms with a lower $k$ (with the complexity $O(n^k)$), see here. You can see how the latest improvements are relatively small, and there is some threshold that won't be crossed.