# CS-113. Problem Set 4

Due Tuesday Oct. 24.

For each of the following programs

1. write a recurrence relation (e.g., counting the number of times that  "junk <-- 2+2" is performed.
2. guess the solution for it (if you need to - for partial credit - approximate as close as you can, e.g. by modifying slightly your answer in (a))
3. prove that your guess in (b) is the correct solution for the recurrence relation in (a) (or its modification in (b).

Note: these programs do not compute anything useful!

You can assume that n is always chosen so that all divisions are even (in this case, the floor() function could have been omitted). The bounds on how your answers might change if this assumption is removed are extra credit (I highly recommend that you at least try).

1. Program P(n):

if n<0 then {
junk <-- 2+2;
return;}

else {

for i=1 to n do { junk <-- 2+2 };
P(n-1);
return; }

1. Program P(n):

if n<1 then {
junk <-- 2+2;
return; }

else {

for i=1 to 100 do { junk <-- 2+2 };
P( floor(n/5) );   %
(if you really get stuck, for partial credit do n/2 instead of n/5)
return; }

1. Program P(n):

if n<1 then {
junk <-- 2+2;
return; }

else {

for i=1 to n do { junk <-- 2+2 };
P( floor(n/2) );
P( floor(n/2) );
return; }

1. Program P(n):

if n<0 then {
for i=1 to 5 do { junk <-- 2+2 };
return; }

else {

for i=1 to n do { junk <-- 2+2 };
P(n-3);
return; }

1. Program P(n):

if n<0 then {
for i = 1 to 5 do { junk <-- 2+2 };
return; }

else {

for i=1 to 4n do { junk <-- 2+2 };
P( n-5 );
return; }