Give example of an algorithm that has 2n running time Big Th

Give example of an algorithm that has (2^n) running time. Big Theta (2^n) NOT Big Oh. Use recursive approach. State expected input, expected output, and detailed time performance analysis. (recurrence relation)

Solution

If n is given as an input, the algorithm outputs all the possible binary numbers of size n.

a is an array of size n. n is the size of the array, curr is an integer.
binary(a,n,curr)
{
   if(curr==n)
   {
       print(a) --> prints the
       return
   }
   a[curr]=0;
   binary(a,n,curr+1);
   a[curr]=1;
   binary(a,n,curr+1);
   return;
}

Initially the function is called with curr = 0;

T(n) = 2*T(n-1) + c