Design and Analysis of Algorithms - 1
Implement a function for each of following problems and count the number of steps executed/Time taken by each function on various inputs and write complexity of each function. Also draw a comparative chart. In each of the following function N will be passed by user.
1. To calculate sum of 1 to N number using loop.
2. To calculate sum of 1 to N number using equation.
3. To calculate sum of 1 to N numbers using recursion.
Code:
#include <stdio.h>
int count_loop=0;
int count_rec=0;
int count_eq=0;
int sum_loop(int n)
{
int i,sum=0;
count_loop++;
for(i=1;i<=n;i++)
{
count_loop++;
sum = sum+i;
count_loop++;
}
return sum;
}
int sum_eq(int n)
{
count_eq++;
int ans=0;
count_eq++;
ans=(n*(n+1))/2;
}
int sum_rec(int n) {
count_rec++;
if (n != 0)
{
count_rec++;
return n + sum_rec(n - 1);
}
else
{
count_rec++;
return n;
}
}
int main() {
int num;
printf("Enter any number:
");
scanf("%d",
&num);
printf("\nSum using loop
= %d", sum_loop(num));
printf("\nTotal number of
steps: %d",count_loop);
printf("\n\nSum using
equation = %d", sum_eq(num));
printf("\nTotal number of
steps: %d",count_eq);
printf("\n\nSum using
recursion = %d", sum_rec(num));
printf("\nTotal number of
steps: %d",count_rec);
return 0;
}
Output:
Analysis Table
Analysis Chart
Conclusion:
In this Practical we learn about variation in Steps Count in various
Function’s like equation, recursion and loop and also about their time
complexity.
There
are different approaches to solve a single particular program.
From
this practical recursion takes highest step as compare to the other Method.
Loop takes a little bit less steps. The Best approach for this practical was
Equation which had very less step and efficient.
Comments
Post a Comment