Time and Space Complexity | Performance Analysis

Time and Space Complexity Performance Analysis

Time and Space Complexity

The performance of an algorithm can be analyzed by two important factors. Those are:

  1. Space complexity :
    The amount of memory space an algorithm needs to run to completion
  2. Time complexity :
    The amount of computer time an algorithm needs to run to completion

Performance evaluation can be done in two phases:

  • A priori estimates
    Before execution estimating the performance
  • A posteriori testing
    After execution measuring performance


Space complexity 


The space needed by an algorithm is the sum of following two components:

 Space Complexity   S(P)=C+SP(I)
 Where C – Fixed Space Requirements (Constant)
 SP(I) – Variable Space Requirements

Fixed Space Requirements (C): i) Independent of the characteristics of the inputs and outputs

    1. Instruction space
    2. Space for simple variables, fixed-size structured variable, constants Variable Space Requirements (SP(I)): i) Depend on the instance characteristic I
      1. number, size, values of inputs and outputs associated with I
      2. recursive stack space, formal parameters, local variables, return address

Considering integer data which needs 1 word of space, we estimate space in no.of words


Example: 1. Sum of n numbers

Algorithm Sum( list, n)
{

tempsum = 0;
for (i := 1 to n do)
tempsum := tempsum + list [i]; return tempsum;
}
S(Sum(n)) >= n+3
    n for list, one each for n, i and tempsum

2. Sum of n numbers (Recursive)

Algorithm Rsum( list], n) 
{ 
if (n<=0)
return 0;
else return Rsum(list, n-1) + list[n]; 
}
S(Rsum(n)) >= 3(n+1)
    Depth of recusrsion is n+1 and Each call to Rsum
    requires 3 words, one each for n, a pointer to list and return address

 

Time complexity

  1. One measure to estimate running time of an algorithm is to determine the no.of additions, subtractions, multiplications, divisions, compares, loads, stores etc.
    Time Complexity T(P) = caADD(n)+csSUB(n)+cmMUL(n)+cdDIV(n) + …
       Where n – no.of instance characteristics Ca – time required for an addition ADD(n) – No.of additions
  2. This approach is not feasible as it depends on the computer system specifications, numbers being added, Operating System etc.
  3. Another approach is to compute the step count. Two methods are available.
    i) First method is to place a count variable and analyze its final value

 Example:

1)  Sum of n numbers

Sum of n numbers

Algorithm Sum( list, n)
{
tempsum = 0;
count:=count+1; // for initializing tempsum for (i := 1 to n do)
{
count:=count+1; // for the ‘for’ stmt tempsum := tempsum + list [i]; count:=count+1; // for tempsum calculation
}
count:=count+1; // for the last time of ‘for’
return tempsum;
count:=count+1; // for the return stmt
}

Answer:  T(Sum(n))>= 2n+3


2)Sum of n numbers (Recursive)


Algorithm Rsum( list], n)
{
count:=count+1; // for ‘if’ stmt
if (n<=0)
{
count:=count+1; // for return stmt return 0;
}
else
{
count:=count+1; // for return stmt return Rsum(list, n-1) + list[n];
}
}

Answer: T(Rsum(n))  = 2                                  if n=0
                                   = 2 + T(Rsum(n-1))       if n>0 The latter one is a recurrence relation
By repeated substitution of T(Rsum) in the relation, we get the following expression:
T(Rsum(n))    = 2 + T(Rsum(n-1))
                       = 2 + 2 + T(Rsum(n-2))
                       = 2n + T(Rsum(0))
                       = 2n + 2

T(Rsum(n)) = 2 if n=0
                      = 2n+2 if n>0

ii) Second method is to build a table listing the total no.of steps.

Time and Space Complexity

 

Topic : Time and Space Complexity

Leave a Reply