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.

  • $\begingroup$ Sounds like a homework, did you tried anything ? $\endgroup$ Jul 28 '13 at 13:24
  • $\begingroup$ @ Bartek :Yes I tried. I read Cormen book 2 times ( Means Chapter Growth Of Function ) ( Sincerely it is confusing me. Book is really tough. ) But when I try new question I become more confused and forget the basics. ( I m preparing this subject for entrance test ) Now see I know Big O , Omega..... with graphical representation but when comes Worst case, best case and Avg case I search those in graphical way like Big o , Omega .... and become confuse. Is worst case mean Theta and Best case mean Big o ?? then what will be its graph ? This sub is really tough. I will die. $\endgroup$ Jul 28 '13 at 14:02
  • $\begingroup$ @ Bartek : 1st option : Value of fun A(n) lies at or below of worst case. But this is not possible as we cant go below worst case as it is already worst. Like this option B also not possible as again value can go below worst case. now option D for this value can be on upper bound of worst case not necessary that it must be below of upper bound of worst case. But option C satisfies condition. Now tell me Am I thinking in right way ? $\endgroup$ Jul 28 '13 at 14:21
  • $\begingroup$ Hey, you seem to ask quite a lot of questions about the asymptotic notations. Did you check out reference questions? Specifically look at the explanations in cs.stackexchange.com/questions/57/… I hope it helps. $\endgroup$
    – Ran G.
    Jul 28 '13 at 20:49

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))$.

  • $\begingroup$ Disclaimer: Landau symbols do not induce total orders. $\endgroup$
    – Raphael
    Jul 29 '13 at 8:02

Not the answer you're looking for? Browse other questions tagged or ask your own question.