# Proving lower bound by proving not little o

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.

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.