Is best case complexity big Omega of worst case complexity?

Question

I need to prove or disprove the following claim:

Given that the best case complexity of the algorithm A is $O(f(n))$ and the worst case complexity of A is $Ω(g(n))$, it follows that $f(n) ∈ Ω(g(n))$.

I know that obviously $A_b \leq A_w$. I can also conclude obviously that for constants $c_1 , c_2$ and for all $n_0 \leq n$ for some $n_0$ the following happens: $A_b \leq c_1f(n)$ and $A_w \leq c_2g(n)$. I can see that it doesn't mean that $f(n) \geq cg(n)$ for some constant $c$ but I am having trouble disproving it. Any help will be welcomed.

Answer 1

Consider the following algorithm $A$:

• If the input consists entirely of zeroes, return.
• Otherwise, count from $1$ to $n^2$, where $n$ is the length of the input.

The best case complexity of this algorithm is $O(n)$, and the worst-case complexity of this algorithm is $\Omega(n^2)$. Does $n = \Omega(n^2)$ hold?