Algorithm Performance Analysis

Whenever a new algorithm is designed, the key fact on which every resource selection of the software implementation is depended upon is the performance analysis. This actually let the programmer/system designer know about the resource consumption by the algorithm. The performance analysis consist up of two main properties:

1. Space Complexity

2. Time complexity

Space Complexity

This analyzes the amount of memory and algorithm needs to run to completion. Speed needed by any algorithm is seen to be the sum of the following components:

a) Fixed part :- This factor is independent of the character of the input and output. This part typically includes the instruction space, space of simple variables and fixed sized component variables, space for constants etc.

b) Variable part :- This consist of the space needed by component variables whose size is dependent on the particular problem instance being solved, the space needed by referenced variables and the recursion stack space included under this.

So overall the fixed part is the one that has a static storage variables whereas variable part consist of those variable which are declared & defined on runtime, also this includes the memory used for recursion stack space used for storing recursive function calls.

So we can say that space requirement S(P) of any algorithm ‘P’ can be written as:

S(P) = C + Sp

Where C -> constant space or fixed part

Sp -> Instance characteristics or variable part

When analyzing the space complexity of an algorithm main concentration is solely on estimating ‘Sp’ i.e. instance characteristics

For any given problem:

(i) We first need to determine which instance characteristics to use to measure the space requirement and this is always problem specific.

(ii) Also it is dependent on quantities related to the number and magnitudes of the inputs and output of algorithms.

(iii) Sometimes more complex measures of the inter-relationship among the data items are used.

Time Complexity

This is the amount of computer time an algorithm needed to run to completion and is most of the time dependent on the Line of code written in any programming language.

Or formally said

The time T(p) taken by a program ‘p’ is the sum of the compile time and the run or execution time. The compile time(static time) does not depend on the instance characteristics, so runtime of the program is mainly considered & is denoted by Tp (instance characteristics)

Some important factors that effects the execution time of a particular program/algorithm are:

1. Characteristics of compiler used to compile the program

2. Machine on which the program is executed & physically clocked.

3. Multiuser environment system

4. No of program steps….. this is the most highlighted factor because it is also responsible for occupying the instruction space which affects the space complexity, but as the compilers are getting advanced this problem is overcome by optimizing the instruction during the compilation process.

Program Step: It is loosely defined as a syntactically or semantically meaningful segment of a program that has an execution time, which is independent of instance characteristics.

The number of steps in any program statement is assigned depends on the kind of statement like, comments count as zero, an assignment statement which does not involves any calls to other algorithm subroutine is counted as one step, in iterative statements we consider the step count only for the control part of the statement including one extra cycle for last iterative call in which the conditional part becomes false and iterative control statement exits without executing the code segment.

There are two ways of determining the step count for the program to solve a particular time complexity of any problem:

1) By adding a count variable in a program initialized with zero and incrementing it after each statement is executed in that program.

2) By building a table in which we list the total number of steps contributed by each statement. This conclusion is often arrived at by first determining the number of steps per execution of the statement & frequency of each statement.

Steps per execution(S/E): The S/E of a statement is the amount by which the count changes as a result of the execution of that statement.

Above discussed topics are very basic or I would say the brief concepts for analyzing the performance of any algorithm. In next post, will try to discuss related to the asymptotic notations which actually produces the concepts closely related to mathematical inductions of analysis part and more signifies the efficiency of any algorithm.

Till then “Happy Reading”