1. Show that big-Theta notation (Θ) defines an equivalence relation on the set of functions.

2. Give the best lower bound that you can for the following code fragment, as a function of the initial value of n.

while (n > 1)

   if (ODD(n))

     n = 3 * n + 1;

else

     n = n / 2;

Do you think that the upper bound is likely to be the same as the answer you gave for the lower bound?

    • 5 years ago
    big-Theta notation
    NOT RATED

    Purchase the answer to view it

    blurred-text
    • attachment
      theta_notation.png
    • attachment
      theta_notation1.png