Question

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?

• A. A(n) = o(W(n))
• B. A(n) = $\Omega$(W(n))
• C. A(n) = $\Theta$(W(n))
• D. A(n) = O(W(n))

Answer 1

The correct option is D A(n) = O(W(n))

A(n) $\to$ Average case complexity
W(n) $\to$ Worst case complexity
We know
Best case $\le$ Average case complexity $\le$ Worst case complexity
and always A(n) $\le$ k. W(n) $\Rightarrow$ A(n) = O(W(n))