2
$\begingroup$

One of my professors mentioned such algorithms exist but could not think of any offhand. Obviously any algorithm will be at least $\mathcal{O(1)}$, but are there algorithms not yet proven to have a lower bound greater than this, which do have a proven upper bound?

I'm interested in both problems and algorithms, but in either case practical examples (if they exist) as opposed to artificial ones.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ It’s easy to construct artificial examples, say an algorithm that looks for a proof of statement X of length at most $n$. If X is provable, then this runs in (essentially) constant time, otherwise in exponential time. $\endgroup$ – Yuval Filmus Mar 20 '19 at 15:47
  • 1
    $\begingroup$ Are you interested in algorithms or problems? $\endgroup$ – Yuval Filmus Mar 20 '19 at 15:47
  • $\begingroup$ @YuvalFilmus Both, I suppose, but in either case practical examples (if they insist) as opposed to artificial ones $\endgroup$ – ubadub Mar 20 '19 at 16:18
  • 1
    $\begingroup$ Can you include all this information in your post? $\endgroup$ – Yuval Filmus Mar 20 '19 at 16:53
  • 1
    $\begingroup$ Note that saying "at least O(_)" is a nonsensical statement, just like "at least something smaller than x". Use $\Omega$, $\omega$, and $\Theta$ to properly express lower buonds. $\endgroup$ – Raphael♦ Mar 21 '19 at 6:51
2
$\begingroup$

To try and answer your question:

Yes. generally lower bound is much harder to prove than upper bound. That is, to prove an upper bound, you must only show one algorithm that solves problem $A$ in $t_1(n)$ time.

To prove a lower bound $t_2(n)$ for the same problem $A$, you must show that ANY algorithm that solves $A$ MUST work in at least $t_2(n)$ time.

Take the median for example (under the comparison model). There is a recursive algorithm that solves the median problem in $O(n)$ time. That means any greater upper bound is moot, and any greater lower bound is wrong.

However a precise lower bound for the median is an open question. The algorithm mentioned above performs $c*n$ comparisons, where $c$ ~ $17$. It has been proven that for selection of median, a total of $\Omega(\frac{3n}{2})$ comparisons is required (which means a better algorithm does not exist).

However, we don't know if a greater lower bound exist. Proving a $\frac{5n}{2}$ comparisons lower bound is an open question!

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ $\Omega$ ignores constant factors. $\endgroup$ – Yuval Filmus Mar 20 '19 at 20:39
  • 1
    $\begingroup$ $2n$ comparison and a bit more is required to find the median as shown by Median Selection Requires (2+epsilon)n Comparisons by Dorit Dor , Uri Zwick. So, this answer does not fully answer the question. $\endgroup$ – John L. Mar 20 '19 at 20:55

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.