4
$\begingroup$

I have seen the formulations

there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time

a problem requires time $n^{2-o(1)}$

a problem requires time $\Omega(n^2)$

being used in the context of lower bounds but I am not sure as to whether there are relevant differences between these notations or if they are simply equivalent. Intuitively, it seems to me like at least the first and third one are while the second one excludes running times like $n^3$ that are included in the others. However, I have also encountered situations where the second one has been used in a similar way to the first one (i.e. the definitions of the Orthogonal Vectors Hypothesis here, p. 6 and here, p. 6) which suggests to me that they are also equivalent. So how do these notations relate to each other?

$\endgroup$
1
  • 2
    $\begingroup$ How about running times such as $n^2/\log n$? $\endgroup$ – Yuval Filmus Oct 8 '20 at 17:04
5
$\begingroup$

It is conjectured that 3SUM cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon > 0$; equivalently, it requires time $n^{2-o(1)}$. This is not the same as the stronger conjecture that 3SUM requires time $\Omega(n^2)$. Indeed, the latter conjecture (which was the original form of the 3SUM conjecture) is false: Grønlund and Pettie came up with an $O(n^2/(\log n/\log\log n)^{3/2})$ algorithm (there were improvements since).

The statement "problem X requires time $n^{2-o(1)}$" states that there exists a function $f(n) = o(1)$ such that any algorithm for X runs in time at least $n^{2-f(n)}$. In particular, there is no $O(n^{2-\epsilon})$ algorithm, for any $\epsilon > 0$. The converse should also hold, I believe – could be a fun exercise to show.

$\endgroup$
2
$\begingroup$
  1. If Your first statement

there is no $\varepsilon>0$ such that a problem can be solved in $O(n^{2−\varepsilon})$ time

we understand as negation of

$\exists\varepsilon>0,f \in O(n^{2−\varepsilon})$

Then it will be $\forall\varepsilon>0,f \notin O(n^{2−\varepsilon})$ which is set $$A=\left\lbrace f:\forall\varepsilon>0, \forall C>0,\forall N\in \mathbb{N}, \exists n>N, f(n) >C n^{2−\varepsilon}\right\rbrace$$ The set from $3$-d statement, $\Omega(n^2)$, as we know, is: $$B=\Omega(n^2)=\left\lbrace f:\exists C>0, \exists N\in \mathbb{N}, \forall n>N, f(n) \geqslant Cn^2 \right\rbrace$$ Now if we consider example $$\phi(n)=\begin{cases} 0, & n=2k-1, k\in \mathbb{N} \\ n^3, & n=2k, k\in \mathbb{N} \end{cases}$$ then $\phi\in A$, but $\phi \notin B$.

  1. For your second statement if set $C=n^{2-o(1)}$ can be defined as $$C=\left\lbrace f: \exists \varepsilon(n), \lim\limits_{n \to \infty} \varepsilon(n)=0, \exists N\in \mathbb{N}, \forall n>N, f(n)= n^{2-\varepsilon(n)}\right\rbrace $$ then again $\phi \notin C$.

So for equivalence there is need some additional restrictions, for example monotonicity, which forbids examples like brought above or we need some other understandings for sets $A,C$.

$\endgroup$
0
$\begingroup$

Beginner myself, but here is my attempt(in Layman terms).

1 ) there is no $ϵ>0$ such that a problem can be solved in $O(n^{2−ϵ})$ time

This means that the problem cannot have a worst solution with an order of growth of at most $cn^k$ where $k\in [0,2)$ and $c$ is some +ve constant.

3 ) a problem requires time $Ω(n^2)$

This means that the best solutions to the problem have an order of growth of at least $cn^2$, $c$ being some +ve constant.

$\endgroup$
12
  • $\begingroup$ Your interpretation of (2) is completely wrong. As for (1) and (3), we are only promised a lower bound in (3) and the non-existence of an upper bound in (1). $\endgroup$ – Yuval Filmus Oct 9 '20 at 9:51
  • $\begingroup$ are my interpretation of (1) and (3) correct? $\endgroup$ – rsonx Oct 9 '20 at 9:59
  • $\begingroup$ The interpretations are basically correct, but in (1) we are ruling out solution with worst-case running time at most $cn^k$, and in (3) we claim that any solution has worst-case running time at least $cn^2$. $\endgroup$ – Yuval Filmus Oct 9 '20 at 10:02
  • $\begingroup$ Edited (1) and (3) . Now? $\endgroup$ – rsonx Oct 9 '20 at 10:11
  • $\begingroup$ Much better. Another fine point is the quantification on $c$, but it is less important. $\endgroup$ – Yuval Filmus Oct 9 '20 at 10:12

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.