Performance analysis of an
algorithm depends upon two factors i.e. amount of memory used and amount
of compute time consumed on any CPU. Formally they are notified as
complexities in terms of: **Space Complexity.****Time Complexity.**
**Fixed Component**: This is independent of the characteristics of the inputs and outputs. This part includes: Instruction Space, Space of simple variables, fixed size component variables, and constants variables.**Variable Component**: This consist of the space needed by component variables whose size is dependent on the particular problems instances(Inputs/Outputs) being solved, the space needed by referenced variables and the recursion stack space is one of the most prominent components. Also this included the data structure components like Linked list, heap, trees, graphs etc.
Therefore the total space requirement of any algorithm 'A' can be provided as
Among both fixed and variable component the variable part is important to be determined accurately, so that the actual space requirement can be identified for an algorithm 'A'. To identify the space complexity of any algorithm following steps can be followed: - Determine the variables which are instantiated by some default values.
- Determine which instance characteristics should be used to measure the space requirement and this is will be problem specific.
- Generally the choices are limited to quantities related to the number and magnitudes of the inputs to and outputs from the algorithms.
- Sometimes more complex measures of the interrelationships among the data items can used.
`Algorithm Sum(number,size)\\ procedure will produce sum of all numbers provided in 'number' list` `{` ` ` ` ` `result=0.0;` ` ` ` ` `for ` `count = 1 to size do \\will repeat from 1,2,3,4,....size times` ` ` ` ` ` ` ` ` `result= result + number[count];` ` ` ` ` `return result;` `}` as 'result','count' and 'size' variable there for total space required is three(3) words.Fixed components
is characterized as the value stored in 'size' variable (suppose value
store in variable 'size 'is 'n'). because this will decide the size of
'number' list and will also drive the for loop. therefore if the space
used by size is one word then the total space required by 'number'
variable will be 'n'(value stored in variable 'size'). Variable components Space(Sum) = 3 + n;
of an algorithm(basically when converted to program) is the amount of
computer time it needs to run to completion. The time taken by a program
is the sum of the compile time and the run/execution time . The compile
time is independent of the instance(problem specific) characteristics.
following factors effect the time complexity:Time Complexity- Characteristics of compiler used to compile the program.
- Computer Machine on which the program is executed and physically clocked.
- Multiuser execution system.
- Number of program steps.
Time(A) = Fixed Time(A) + Instance Time(A)Here the number of steps is the most prominent instance characteristics and The number of steps any program statement is assigned depends on the kind of statement like - comments count as zero steps,
- an assignment statement which does not involve any calls to other algorithm is counted as one step,
- for iterative statements we consider the steps count only for the control part of the statement etc.
: Time ComplexityExample
In above example if you analyze carefully frequency of " `for count = 1 to size do` "
it is 'size +1' this is because the statement will be executed one time
more die to condition check for false situation of condition provided
in for statement. Now once the total steps are calculated they will
resemble the instance characteristics in time complexity of algorithm.
Also the repeated compile time of an algorithm will also be constant
every time we compile the same set of instructions so we can consider
this time as constant 'C'. Therefore the time complexity can be
expressed as: Time(Sum) = C + (2size +3) So
in this way both the Space complexity and Time complexity can be
calculated. Combination of both complexity comprises the Performance
analysis of any algorithm and can not be used independently. Both these
complexities also helps in defining parameters on basis of which we
optimize algorithms. |