What do you mean by complexity of algorithms? How do you find time complexity?

Answers

This answer is not selected as best answer. This answer may not be sufficient for exam.

Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.

Quota: 0 / 30

Donate

The complexity of an algorithm is a function f (n) which measures the time and space used by an algorithm in terms of input size n. The complexity of an algorithm is a way to classify how efficient an algorithm is, compared to alternative ones.

The process of finding complexity of given algorithm by counting number of steps and number of memory references used by using RAM model is called detailed analysis. For detailed time complexity algorithm we count the number of steps and finally add all steps and calculate their big oh notation. Similarly for detailed analysis of space complexity we count the number of memory references and finally add all steps and find their big oh notation.

#include<stdio.h>

int main()
{

    int i, n, fact=1;

    printf("Enter a number to calculate factorial:");

    scanf("%d",&n);

    for(i=1; i<=n; i++)
        fact = fact*i;

    printf("Factorial of %d=%d", n, fact);
    return 0;

}

Time Complexity:

The declaration statement takes 1 step.

Printf statement takes 1 step.

Scanf statement takes 1 step.

In for loop:

i=1 takes 1 step

i<=n takes (n+1) step

i++ takes n step

within for loop fact=fact*i takes n step

printf statement takes 1 step

return statement takes 1 step

Total time complexity = 1+1+1+1+n+1+n+n+1+1

= 3n+7

= O(n)

Space complexity:

total memory references used = 3 = O(1)

If you found any type of error on the answer then please mention on the comment or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .