1
$\begingroup$

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.

$\endgroup$
1
1
$\begingroup$

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?

$\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.