2
$\begingroup$

I have been reading these distributed computing notes. In some of the proofs, for proving lower bound of $\Omega(f(n))$, we prove that no algorithm which solves the problem in $o(f(n))$ exists.

I can't see how not having a $o(f(n))$ algorithm proves the lower bound is $\Omega(f(n))$.

I tried using the definitions, but not having an $o(f(n))$ algorithm implies, for all algorithms $\exists c>0 $ such that $\forall n_0 \exists n \geq n_0$ such that there exists an input of size $n$ which takes at least time $cf(n)$.

For $\Omega(f(n))$, we would require $\exists c>0,n_0 $ such that $\forall n \geq n_0$ there exists an input of size $n$ which takes at least time $cf(n)$.

Any help is appreciated, thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

Your confusion is completely justified.

When we say that some problem $A$ has a lower bound of $\Omega(f(n))$ usually we mean that "No algorithm that runs in time $o(f(n))$ solves $A$" or equivalently, "there is an infinite class of instances for which any algorithm that solves $A$ requires time at least $cf(n)$ for some constant $c>0$".

This matches the Hardy-Littlewood version of the $\Omega(\cdot)$ notation.

This is in contrast with "any algorithm that solves $A$ requires time at least $cf(n)$ on all sufficiently large instances", which is what you were expecting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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