big-Theta notation
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?