from the each given code below state whether is a valid recu

from the each given code below, state whether is a valid recursion or not. if it is valid give Big(O). if it is not valid recursion, why?.

1. int f (int n)

{

if (n<= 0)

return 0;

else

return f(n/3 +1)+ n-1;

}

2. if g (int n)

{

if (n<= 0)

return 0;

else

return g(n/2) + n;

thanks:

Solution

1. int f(int n)                                        

{

    if (n<= 0

       return 0;

      else

         return f(n/3 +1)+ n-1;

   }

This is not valid recursion. It is not possible to exit from recursion

For example:

N=10

Round1: N=10/3 +1=4

Round2: N=4/3 +1=2

Round3: N=2/3 +1=1

Round4: N=1/3 +1=1

.

.

. etc

Ther is no end to recursion int f(int n)

2. int g (int n)

{

   if (n<= 0)

      return 0;

   else

      return g(n/2) + n;

}

This is valid recustion, It is valid give Big(O),

T(N/2)+ O(N)= O(log N).

For Example: N=10

Round1: N=10/2=5

Round2: N=5/2=2

Round3: N=2/2=1

Round4: N=1/2=0

Round5: return 0

It is valid give Big(O)=T(N/2)+ O(N)= O(log N).