Topic: Discrete Mathematics "Advanced Counting Techniques"

1. Let an be the number of arithmetic operations (i.e., additions, subtractions, multiplications and

divisions) executed by the following pseudocode for an input integer n 0. Show how you construct a recurrence system on an.

 Line# Pseudocode 

function mystery(n: integer): integer;

// Given a nonnegative integer n, return an integer. 

k: integer;

ifn=0thenreturn1

else if n = 1 then 1 + return mystery(0)

else {

k := 5 + mystery(n-1);

return (2k) mystery(n-2)

}

2. Let an be the number of additions executed by the following pseudocode for an input integer n 0. Show how you construct a recurrence system on an.

function mystery(n: integer): integer; // Given a nonnegative integer n, return an integer. if n = 0 then return 0 else if n = 1 then 1 else return mystery(n-1) + mystery(n-2)