Multiple choice running time of algorithm

Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. which of the following is ALWAYS TRUE?

  1. A(n) = $\Omega$ W(n)
  2. A(n) = $O$ W(n)
  3. A(n) = $\Theta$ W(n)

  4. A(n) = o W(n)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Average-case running time $A(n)$ is bounded above by the worst-case running time $W(n)$ for all inputs of size $n$, because the average value of a set cannot exceed its maximum. Therefore, $A(n) = O(W(n))$ always holds. The other options are false because the average case can be asymptotically strictly smaller than the worst case.

Keep practicing — related questions