3
$\begingroup$

Are there any problems where there is no smallest time complexity, so there is a big-$\mathcal{O}$ but no big-$\Theta$?

More formally, I am looking for any problem $p$ where

  • for any algorithm that solves $p$ in time $f(n)$
  • there provably exists another algorithm that solves $p$ in time $g(n)$
  • where $g(n) = o(f(n))$.

An example would be a problem for which there exist algorithms of complexity $\mathcal{O}(n^k)$ for all $k > 0$, but for which there is no algorithm of lower complexity, like $\mathcal{O}(1)$ or $\mathcal{O}(\log n)$.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ There is no $<$ relation between $O(f)$ and $O(g)$, you could use the little $o$ notation and say $g(n)=o(f(n))$. One example for what you required in your last statement could be finding an element in a sorted array. I think this post answers the question in the title. $\endgroup$ – Ariel Dec 8 '17 at 12:20
  • $\begingroup$ @Ariel Thanks, I've never heard of Blum's Speedup Theorem before. I fixed the niggles in the post as well. $\endgroup$ – Veedrac Dec 8 '17 at 12:36
3
$\begingroup$

The existence of such problems follows from the Blum speedup theorem. The theorem shows, for example, that there exists a problem such that for any algorithm solving it in time $T(n)$, there is another one solving it in time at most $\log T(n)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks. Are there any good examples? I don't have time to read the proof right now. $\endgroup$ – Veedrac Dec 8 '17 at 12:37
  • $\begingroup$ Not really. The examples constructed by the theorem are very contrived. $\endgroup$ – Yuval Filmus Dec 8 '17 at 12:40
1
$\begingroup$

You might be interested in something similar to what you are describing (in terms of a hierarchy of algorithms of different runtimes that get closer and closer to some limiting runtime). Polynomial time approximation schemes (PTAS) have runtimes stated like $O(2^{1/\epsilon}n^2)$ or $O(n^{1/\epsilon})$ for any epsilon, and you are sort of free to pick your epsilon as a trade-off between the runtime or the accuracy to an approximate solution.

See http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course%20Notes/lecture7.pdf for an intro to PTAS and an example showing a $O(n^3/\epsilon)$ PTAS for a solution to Knapsack which is at least $(1-\epsilon)\times OPT$

|cite|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.