Exercise IV

  • Use the mathematical definition of Big-Oh to prove the asymptotic running time of a given program.

Consider the following facts:

  • Baby chicken might be larger than baby turkey at the beginning.
  • But after a certain "breakpoint," the chicken size will be surpassed by the turkey size.
  • From the breakpoint on, the chicken size will always be smaller than the turkey size.

Exercise Which statement is true?

A) chicken size is in O(\Omicron(turkey size)).
B) turkey size is in O(\Omicron(chicken size)).

Solution

Chicken's growth order is smaller than turkey's, or chicken size is in O(\Omicron(turkey size)).

The breakout point is the n0n_0 in the mathematical definition of Big-Oh.