Time complexity and Space complexity

Time complexity 

Definition : Amount of time required by an algorithm                         to execute is called time complexity.

Time complexity is the amount of time taken by the program for execution.As it is difficult to measure the time complexity in terms of clock units,we will measure the time complexity using the frequency count.

FREQUENCY COUNT: The efficiency of a program is measured by inserting a counter in the algorithm in order to count the number of times the basic operation is executed. this is a straightforward method of measuring the time complexity of the program. 

EX.

1)consider following piece of the code for obtaining the frequency count-

void display()

{

    int a,b,c;

    a=10;

    b=20;

    c=a+b;

    printf("%d",c);

}

solution:

2)find the frequency count of:

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

   for(j=1;j<=i;j++)

    x=x+1;

solution:

Space complexity

Definition: Amount of storage required by an                       algorithm is called space complexity.

space complexity can be defined as  amount of memory required by an algorithm.

It compute the space complexity we use two factors: constant and instance

                                      s(p)=C+s(p)

c is a constant.fixed part and it denotes the space of input and outputs.this is an amount of space taken by instruction,variable and identifiers.And sp is a space dependent upon instance characteristics.This is a variable part whose space requirement depends on particular problem instance.

fixed part includes space for:

• instructions
• variable
• Array size
• Space for constant

variable part includes space for:

• Recursion stack for handling recursive call.
• The variable whose size is dependent upon the particular problem instance being solved. The control statements (such as for,do,while,choice) are used to solve such instance.

EX.

compute the space complexity for the code fragment:

Algorithm sum(a,n)

{

   s:0.0; 

     for i: 1 to n do

          s: s + a[i];  

            return s;

}

solution:

given code we require space for:

   

s: =0   require 1 unit of space

for i:  to n   require n unit of space

s: s + a[i];   require n units of space

returns;   require  units of space

thus total 2n+2 units of space is required.if we neglect the constants of this equation and if consider the order of magnitude then the space complexity is denoted using Big Oh notation as O(n).