Data Structures and Algorithms - Old Questions

11. How to find complexity of algorithms? Explain.

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.

E.g.

#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)