How can we compute best-case and/or average-case and/or worst-case running-time knowing some of them?

Question

Complete the table when it is possible.

$$ \begin{array}{c|lcr} \mathrm{Algorithme} & \text{worst-case} & \text{average-case} & \text{best-case} \\ \hline A & O(n) & ... & \Omega(n) \\ B & \Omega(n^2) & ... & \Omega(n^3) \\ C & ... & \Theta(n^2) & ...\\ D & O(n^2) & ... & \Omega(n^3)\\ E & \Omega(n^2) & ... & O(n) \end{array} $$ I tried this:

Let $T(n)$, $B(n)$, and $A(n)$ be the worst-case, best-case, and average-case running times, respectively.

• For algorithme A, we have:

  • $T(n)\leqslant c_1n$,
  • $B(n)\geqslant c_2n$,
  • $B(n)\leqslant A(n)\leqslant T(n)$.

  Then, $A(n)=\Theta(n)$.

• For algorithme B, we have:

  • $T(n)\geqslant c_1n^2$,
  • $B(n)\geqslant c_2n^3$,
  • $B(n)\leqslant A(n)\leqslant T(n)$.

  Then, $A(n)=\Omega(n^3)$.

• For algorithme C, we have:

  • $c_1n^2\leqslant A(n)\leqslant c_2n^2$,
  • $B(n)\leqslant A(n)\leqslant T(n)$.

  Then, $T(n)=\Omega(n^2)$ and $B(n) = O(n^2)$.

• For algorithme D, we have:

  • $T(n)\leqslant c_1n^2$,
  • $B(n)\geqslant c_2n^3$,
  • $B(n)\leqslant A(n)\leqslant T(n)$.

  Then, Absurd.

• For algorithme E, we have:

  • $T(n)\geqslant c_1n^2$,
  • $B(n)\leqslant c_2n$,
  • $B(n)\leqslant A(n)\leqslant T(n)$.

  Then, we cannot say anything.

Am right in my answers? If no, can you please explain to me. Thanks.

Answer 1

You are correct. In the cases that were not "absurd" you cannot do better. The absurd cases can not be determined without some knowledge of how often are runs good and how often are they bad.