I need an example of a program that contains an algorithm wh

I need an example of a program that contains an algorithm whose Big- is exponential. Please explain what n represents in the program. Make some assumption about how long it would take to execute one of the operations that you are counting. Determine how large n would have to be so that the time required would exceed a million years. Is there a more efficient algorithm that will solve the same problem? If so, describe it.

Solution

Binomial Coefficient:

#include<stdio.h>

int binomialCoeff(int n, int k)
{
  
if (k==0 || k==n)
return 1;

  
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
int main()
{
int n = 5, k = 2;
printf(\"Value of C(%d, %d) is %d \", n, k, binomialCoeff(n, k));
return 0;
}

==================================================

Above code complexity is O(2ⁿ)

Explanation: n is decreased by one every step.As we can see no of calls doubles each time.It will happen till n=1.Hence C(n,k) is called at most 2ⁿ times.

all operations in one C(n,k) call run in O(1) (constant time),

Hence n should be million number to exceed a million years time.

=======================================================

More efficient

#include<stdio.h>

int BinoC(int n, int k)
{
int T[n+1][k+1];
int i, j;

for (i = 0; i <= n; i++)
{
for (j = 0; j <= min(i, k); j++)
{

if (j == 0 || j == i)
T[i][j] = 1;

else
T[i][j] = T[i-1][j-1] + T[i-1][j];
}
}

return T[n][k];
}

int main()
{
int n = 20, k = 20;
printf(\"Value of C(%d, %d) is %d \", n, k, BinoC(n, k));
return 0;
}

==================================================

time complexity is: O(n*k)

re-computations of same subproblems is avoided by a temporary array T[][] in bottom up manner.

We can there are 2 loops in code hence it is more efficient than exponential algorithm