Exercise VII

  • Recognize that Big-Oh and big Omega are not necessarily tight bounds.
  • Recognize growth rate type (upper or lower bound) is different from worst-case vs. best-case analysis.

Exercise Which of the following statements are correct? (There may be more than one correct answer!)

A) Big-Oh describes the worst-case, whereas big Omega describes the best-case running time.
B) Big-Oh describes the upper bound, whereas big Omega describes the lower bound on the worst-case running time.
C) Big-Oh and big Omega can describe either upper or lower bound, but typically we use Big-Oh for upper bounds and big Omega for lower bounds.
D) Big-Oh and big Omega can be used to describe best-, average- or worst-case running time.

Solution

The correct answers are (B) and (D)