# 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?

• also the sorting problem assumes in the proof that the algorithm is based on comparison. So does this proof says: "There cannot exists an algorithm (comparison-based or not) that solves the problem in less than log(n)*n time?" If not then this isn't even a lower bound to the full problem...? – test1000000 Oct 3 '16 at 0:05
• You can sort integers in $o(n\log n)$ [on a RAM machine], so some restriction is needed if you want to obtain a lower bound of $\Omega(n\log n)$. – Yuval Filmus Oct 3 '16 at 14:41

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