Topic: Discrete Mathematics "Advanced Counting Techniques"

1. Show how you construct a recurrence system on the function computed by the following recursive

algorithm Mystery.

function Mystery(n: integer): integer; // Given a positive integer n, return an integer.

i: integer; if n =1then return1 else begin

i := 0;

while 2i < n do i := i + 1;

return i + n2 + Mystery( n/2 )

end

2. Let f(n) be the number of modular multiplications (i.e., (x y) mod m) executed by the following recursive algorithm. Show how you construct a recurrence system on f(n) and derive a Big-O estimate of f(n).

procedure mpower(b, n, m: integer); {InitialAssertion:b Z+n Nm Z+} if n = 0 then

mpower(b,n,m) = 1 else if n mod 2 = 0 then

mpower(b,n,m) = mpower(b,n/2,m)2 mod m else mpower(b,n,m) = ((mpower(b, n/2 ,m)2 mod m)(b mod m)) mod m

{ Final Assertion: mpower(b,m,n) = bn mod m }