Give a recurrence relation for the runtime of the following functions (and pleas

Question

Give a recurrence relation for the runtime of the following functions (and please walk me through why!):

1. int fun1(int n) {

   if (n==1) return 50;

   return fun1(n/2) * fun1(n/2) + 97;

   }

2. int fun2(int n) {

   if (n==1) return 1;

   int sum=0;

   for (int i=1; i<=n; i++)

      sum += fun(n-1);

   return sum;

   }

3. int fun1(int n) {

if (n==1) return 1;

return fun1(n/2) * fun1(n/2) + 1; }

4. int fun2(int n) {

if (n==1) return 1;

int sum=0;

for (int i=1; i<=n; i++)

sum *= fun(n-2);

return sum; }

Explanation / Answer

int fun1(int n) {

if (n==1) return 50;

return fun1(n/2) * fun1(n/2) + 97;

}

Recurrence relation : T(n) == T(n/2)+T(n/2) = 2T(n/2) // because recursive call is dividing the the size of n by half two times.

int fun2(int n) {

if (n==1) return 1;

int sum=0;

for (int i=1; i<=n; i++)

sum += fun(n-1);

return sum;

}

Recurence Relation = T(n) = n*T(n-1) //because from each iteration from 1 to n there is recursive call for n-1.

int fun1(int n) {

if (n==1) return 1;

return fun1(n/2) * fun1(n/2) + 1; }

Recurrence relation : T(n) == T(n/2)+T(n/2) = 2T(n/2) // because recursive call is dividing the the size of n by half two times.

int fun2(int n) {

if (n==1) return 1;

int sum=0;

for (int i=1; i<=n; i++)

sum *= fun(n-2);

return sum; }

Recurence Relation = T(n) = n*T(n-2) //because from each iteration from 1 to n there is recursive call for n-2.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.