Due: Monday, May 24.
Exercise 2-3, page 39 of the text. Assume that additions and multiplications of numbers take constant time. The "asymptotic" time is the time to within a constant factor, for large inputs. That is, use big-O notation. A loop invariant is an assertion about the values of the variables that is true whenever the loop is at its top.
Exercise 3-4(a,b,g). Notice that you are asked either to prove or to disprove each assertion. So think about whether each is true or false. If the conjecture is false, it suffices to give a counterexample. If it is true, give an argument why it must be true for all functions. Hint for part (g): Think about functions that grow very fast, such as 2n.