===========================================================================
CSC 236               Problem set 3                               Fall 2008
===========================================================================

Consider the following algorithm that computes x^y for x, y in N:

    pow(x, y):
        if y == 0:
            return 1
        elif y % 2 == 0:
            t = pow(x, y/2)
            return t * t
        else:
            t = pow(x, (y-1)/2)
            return t * t * x

A.  Give a recurrence relation for the worst-case running time of pow().
    Define n precisely (as a function of x and/or y), and briefly justify
    that your recurrence is correct (based on the algorithm).

B.  Perform repeated substitution to guess a closed form for your
    recurrence in the case when y is a power of 2.

C.  Now do B without any assumptions on y. (this is little bit beyond the 
    usual level of questions I like to ask in problem sets and will be 
    graded accordingly.)