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?
2
$\begingroup$
$\endgroup$
-
$\begingroup$ 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...? $\endgroup$ – test1000000 Oct 3 '16 at 0:05
-
$\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Oct 3 '16 at 14:41
5
$\begingroup$
$\endgroup$
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.
answered Oct 3 '16 at 5:56
