Making sense of asymptotic notation 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 &amp; &lt; \\
O &amp; \leq \\
\Theta &amp; = \\
\Omega &amp; \geq \\
\omega &amp; &gt;
\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 &gt; 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))$.