Multiple choice

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) =$\odot$(W(n))

  3. A(n) = O(W(n))

  4. None of these
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

If B(n), A(n) and W(n) denote best case, average case and worst case time complexities of an algorithm P respectively then B(n) = O(A(n)) , A(n) = O(W(n))

Keep practicing — related questions