Question

6. Using big-oh notation, give the runtime for each of the following recursive functions. You do not need to justify your answers: a) Int nonesense (int n) if (n <0) return 1; return nonsense (n-2) 1; b) int no nonesense (int n) if (n <0) return 1; return no_nonsense (n-1)+ no nonsense (n-1)

Answer 1

1.)int nonsense( int n){

if(n<0)

return 1;

else

return nonsense(n-2)+1;

}

Explanation:

If n=0, T(n)=1

If n>=0,T(n)=a+T(n-2) //where a is a constant and T(n-2)

By Induction Method,

T(n)=a+T(n-2)=a+ceil(n/2) i.e equivalent to =O(n)

so timecomplexeity is O(n) for equation 1

2.

int no_nonesense(int n){

if(n<0) return 1;

return no_nonsense(n-1)+no_nonsense(n-1);

}

Explanation:

T(n)=T(n-1)+T(n-1)+a where a= constant

=2T(n-1)+a;

By induction,

T(n)=2ceil(n)+a i.e=2 O(n)+a were a is a constant

i.e equivalent to O(n)

So the time complexeity for 2nd expression is also O(n) by induction