Question

Let function F(n, m) outputs n if m = 0 and F(n, m − 1) + 1 otherwise.

1. Evaluate F(10, 6).

2. Write a recursion of the running time and solve it

. 3. What does F(n, m) compute? Express it in terms of n and m.

Answer 1

1)

F(n,m) = 1+F(n,m-1)

F(10,6) = 1+F(10,5)

= 1+(1+F(10,4))

= 2+F(10,4)

= 2+(1+F(10,3))

= 3+F(10,3)

= 3+(1+F(10,2))

= 4+F(10,2)

= 4+(1+F(10,1))

= 5+F(10,1)

= 5+(1+F(10,0))

= 6+F(10,0)

= 6+10 (F(n,0) returns n)

= 16

2)

The above function can be represented as follows:

F(n,m){

if(m=0)

return n;

else

return 1+F(n,m-1);

}

Therefore the recurrence relation would be

T(n,m) = T(n,m-1) + 1

= (T(n,m-2) + 1) + 1

= T(n,m-2) + 2

= (T(n,m-3) + 1) +2

= T(n,m-3) + 3

=T(n,m-k) +k (in general form)

we know that T(n,0)=1 because the function takes only one unit of time to return n value.

let m-k = 0 => m=k

substitute m=k in the above recurrence relation.

T(n,m) = T(n,0) + m

= 1 + m

Therefore the running time of the function F(n,m) is m+1

3)

F(n,m) computes the addition of n and m values.

F(n,m) = F(n,m-1) + 1

= (F(n,m-2) + 1) + 1

= F(n,m-2) + 2

= (F(n,m-3) + 1) +2

= F(n,m-3) + 3

= F(n,m-4) +4 and so on we continue up to F(n,m-m) + m

=> F(n,m) = F(n,0) + m = n+m