Tn is defined recursively as Tn 2 middot sigmai 1n 1 Ti i

T(n) is defined recursively as T(n) = {2 middot sigma_i = 1^n - 1 T(i) if n = 1, otherwise What is the order of T(n)l In other words, find an expression (n) such that T(n) = 0(f(n)). You now implement the function recursively. Write down your recursive implementation. What is the time complexity of your algorithm?

Solution

Here is the code in C implementing the recursive algorithm for the given definition of T(n). The function T(n) will be called \'n\' times depending on the value of n. Hence the algorithm is of O(n) time complexity.

#include <stdio.h>

int T(int n)
{
   int result=0;
   if(n==1)
       return 1; /* T(n) = 1 for n=1 is given */
   else
   {
       /*calculate sum of T(n-1)+T(n-2)+......+T(1) recursively */
       for(;n>1;n--)
       {
           result+=T(n-1);
       }
      
       /*now multiply the sum by 2 as given in the definition of T(n) = 2* sum( T(n-1)+ T(n-2)....+T(1) )*/
       result=2*result;
      
       return result;
   }
}

int main()
{
   int n,ans;
  
   printf(\"\ Enter a number : \");
   scanf(\"%d\",&n);
  
   /*call the recursive function and display the reuslt.*/
   ans=T(n);
   printf(\"\ T(%d) = %d\", n,ans);
  
  
   return 0;
}