Traditionally Modern Analysis - Complexity Analysis

Following is the current performance testing life cycle which we already know,        

• Step – 1: Non-Functional Requirements Elicitation and Analysis
• Step – 2: Performance Test Strategy
• Step – 3: Performance Test Design
• Step – 4: Performance Test Execution
• Step – 5: Performance Test Result Analysis
• Step – 6: Benchmarks and Recommendations

In this blog, I would like to introduce one more step into the above performance testing life cycle “Complexity Analysis” after the Step – 5.  We’ll discuss Complexity Analysis in brief here,

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

Time and space complexity depends on lots of things like hardware, operating system, processors, etc.

The order of growth is how the time of execution depends on the length of the input. The time of execution linearly depends on the amount of data. The order of growth will help us to compute the running time with ease.

Space Complexity of an algorithm is the amount of memory it needs to run to completion i.e. from start of execution to its termination. Space need by any algorithm is the sum of the following components:

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

Space(A)  = Fixed Components(A) + Variable Components(A)

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.

Time Complexity 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 affect the time complexity:

• Characteristics of the compiler used to compile the program.
• Computer Machine on which the program is executed and physically clocked.
• Multiuser execution system.
• The number of program steps.

Therefore the again the time complexity consists of two components fixed(factor 1 only) and variable/instance(factor 2,3 & 4),  so for any algorithm 'A' it is provided as:

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.

Therefore to calculate the total number program of program steps we use the following procedure. For this, we build a table in which we list the total number of steps contributed by each statement. This is often arrived at by first determining the number of steps per execution of the statement and the frequency of each statement executed.

Types of algorithms that may need performance testing:

There are several types of algorithms that may need performance testing to try to ascertain whether the developer used industry best practices. Each of these categories of work needing to be performed can be categorized based on roughly how much longer the processing should take as the data set increases in size.

• Searching one or more large data sets to find data elements matching certain criteria, to include creation and execution of complex ad-hoc data queries
• Sorting a large data set into a particular sorted order
• Merging two or more data sets, at least one of which is large, with resultant list possibly in some sorted order
• Optimization algorithms which seek to determine optimally routing of a delivery vehicle to visit multiple locations (for example, a optimizing a bomber route as it flies over or near multiple targets)