Let \(W(n)\) and \(A(n)\) denote respectively, the worst case and average…
2012
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) = Ω (W(n))\) - B.
\(A(n) = Θ (W(n))\) - C.
\(A(n) = O (W(n))\) - D.
\(A(n) = o (W(n))\)
Attempted by 414 students.
Show answer & explanation
Correct answer: C
Key insight: the average-case running time A(n) is never larger than the worst-case running time W(n) for the same input size.
For every input of size n, the running time T(x) ≤ W(n) by definition of worst-case.
The average A(n) is the mean of those T(x) values, so A(n) ≤ W(n) for all n.
Therefore A(n) = O(W(n)) (take constant c = 1 and any n0), which means the average-case grows no faster asymptotically than the worst-case.
Note: this does not imply that average and worst are equal (Θ) or that average is always strictly smaller (o); concrete algorithms can show those possibilities both occur.
A video solution is available for this question — log in and enroll to watch it.