Let W(n) and A(n) denote respectively, the worst case and

Home » Theory of Computation » Theory of computation miscellaneous » 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?

1. A(n) = Ω (W(n))
2. A(n) = Θ (W(n))
3. A(n) = O (W(n))
4. A(n) = o (W(n))

Correct Option: C

As we have given,
A(n) → Average case complexity
W(n) → Worst case complexity
As we know that average case will always be less than or equal to worst case complexity.
A(n) ≤ W(n)
Consider option (a) :
A(n) = Ω (W(n))
∴ It says W(n), worst case complexity is less than the average case complexity which is wrong because Ω asymptotic notation shows (≥) sign. Hence, this option is false.
Consider option (b) :
A(n) = θ (W(n))
∴ It says A(n), worst case complexity is same as worst case complexity because θ notation shows equality sign. Hence, this is false.
Consider option (c) :
A(n) = O (W(n))
∴ It says that average case complexity A(n) is less than or equal to W(n) worst case complexity. Hence, this option is correct.
Consider option (d) :
A(n) = O (W(n))
∴ It says that A(n) is strictly less than W (n), so this option is false.