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) = \Omega(W(n))$
(B) $A(n) = \Theta(W(n))$
(C) $A(n) = O(W(n))$
(D) $A(n) = o(W(n))$
Answer: (C).
What do all these options "mean"? I find it hard to reconcile the graphs exemplifying asymptotic notation and abstract situations such as this one.
The easiest way to remember asymptotic notation is to memorize the following table: $$ \begin{array}{cc} o & < \\ O & \leq \\ \Theta & = \\ \Omega & \geq \\ \omega & > \end{array} $$ For example, if $f(n) = O(g(n))$ then asymptotically and up to a constant multiple, $f(n) \leq g(n)$; formally, there exists a constant $C > 0$ such that $f(n) \leq Cg(n)$ for large enough $n$. In your case, clearly the average case is at most the worst case, and so $A(n) = O(W(n))$.
