Examples for lower bounds proof except sorting After i read this question here.

All non-trivial examples of lower bounds always mention sorting, but i do not find other non-trivial examples, which do not rely (partly) on the sorting proof.

What are other non-trivial examples?
Here are some examples:


Finding an element in a sorted list takes time $\Omega(\log n)$ in the RAM model.
Implementing a disjoint sets data structure requires an amortized $\Omega(\alpha(n))$ operations in the cell probe model.
Determining whether the input string is a palindrome requires $\Omega(n^2)$ operations on a single tape Turing machine.


There are many others.