2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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$

Here are some examples:

  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.

There are many others.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.