Project ForgeLet 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?
- AA(n) = Ω(W(n))
- BA(n) = Θ(W(n))
- A(n) = O(W(n))
- DA(n) = o(W(n))
Explanation
By definition, worst-case time is the maximum over all inputs of size n, so average-case time can never exceed it: A(n) ≤ c·W(n), i.e. A(n) = O(W(n)) — true for every algorithm, always. The Ω, Θ, and o relations are NOT guaranteed in general (e.g. quicksort's average case is Θ(n log n) while its worst case is Θ(n²), so A(n) is not Ω(W(n)) or Θ(W(n)) there, and can't be o(W(n)) either since equality is possible for some algorithms).
Source: GATE CS 2012 (2012)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.