Performance analysis(Time & Space Complexity)

ADA || DAA || Performance analysis || Time Complesity || Space Complexity || Swapna.C

1. ALGORITHM DESIGN AND ANALYSIS SWAPNA.C

2. Performance of a program: The performance of a program is the amount of computer memory and time needed to run a program. We use two approaches to determine the performance of a program . One is analytical, and the other experimental . In performance analysis we use analytical methods, while in performance measurement we conduct experiments. Performance Analysis: Performance Analysis of an algorithm depends upon 2 factors that is amount of memory used and amount computer time consumed on any CPU. Space complexity, Time Complexity, Network ,Power, CPU Registers.

3. Time Complexity The time needed by an algorithm expressed as a function of the size of a problem is called the time complexity of the algorithm. The time complexity of a program is the amount of computer time it needs to run to completion. Time=Fixed Time +Instance time. Characteristics of compiler used to compile the program.{fixed}. Computer Machine on which the program is executed and physically clocked.{variable} Multiuser execution system. {variable} Number of program steps. {variable} The limiting behaviour of the complexity as size increases is called the asymptotic time complexity . It is the asymptotic complexity of an algorithm, which ultimately determines the size of problems that can be solved by the algorithm.

4. Comments count as zero steps. As 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. Calculate: Total no. of program steps= no. of steps per execution of the statement + frequency of each statement executed.

5. Statement Steps for execution Frequency Total steps Algorithm sum ( number, size) - { - Result:=0.0 1 1 1 For count=1 to size do 1 size+1 size+1 result= result + number[count]; size size Return result; 1 1 1 } Total 2size+3 Time Complexity:

6. Step Table

7. Space Complexity The space complexity of a program is the amount of memory it needs to run to completion i.e from start of execution to its termination. . The space need by a program has the following components: Fixed component + Variable component=space. Fixed Component: Instruction space+ space of sample variable + constant variable. This is independent of input and output. Variable component: space needed by compound variable whose size depend on input and output. EX: stack space, data structures like linked list, heap, trees graphs. Instruction space: Instruction space is the space needed to store the compiled version of the program instructions. Data space: Data space is the space needed to store all constant and variable values. Data space has two components: Space needed by constants and simple variables in program. Space needed by dynamically allocated objects such as arrays and class instances.

8. Environment stack space: The environment stack is used to save information needed to resume execution of partially completed functions. Instruction Space: The amount of instructions space that is needed depends on factors such as: The compiler used to complete the program into machine code. The compiler options in effect at the time of compilation The target computer. To calculate: 1.Determine the variables which are instantiated by some default values. 2.Determine which instance characteristics should be used to measure the space requirement and this will be problem specific. 3.Generally the choices are limited to quantities related to the number and magnitudes of the inputs to and outputs from the algorithms. 4.Some times more complex measures of the inter realtionships among the data items can used.

9. Ex: Algorithm Sum(number[], size) { result:=0.0; result-------------------1 word for count:=1 to size do count---------------1unit size------1 unit result:=result + number[count]; number[]----------n return result; } S(n)=3+n---------------O(n) Constant space complexity: Ex. Algorithm square( int a) a variable -----1 { return a*a;-------------s(n)=1}------------------O(1) Linear space complexity: Ex.int sum( int a[], int n) n variable ---1unit int sum=0; a---n units for( i =0;i< n;i ++) i --------1 unit sum= sum+a [ i ]; sum--- 1 unit return sum } s(n)=n+3----------O(n)

10. Ex: Algorithm Swap( a,b ) Space Time { Temp=a: ---------1word 1 unit of Time a=b; ----------1 1 b=Temp; -------1 1 } s(n)=3 f(n)=3 Ex: Ex.int sum( int a[], int n) Space Time { n variable ---1unit int sum=0; a---n units 1 for( i =0;i< n;i ++) { i --------1 unit n+1 sum= sum+a [ i ]; } sum--- 1 unit n return sum 1 } s(n)=n+3----------O(n) f(n)=2n+3-------O(n)

11. Frequency Count Method Ex: Algorithm Add( A,B,n ) Time Space { for( i =0;i< n;i ++) n+1 A---n^2 { B---n^2 for(j=0;j< n;j ++) n*(n+1) C---n^2 { n--1 C[ i,j ]=A[ i,j ]+B[ i,j ]; n*n i ---1 } j---1 } f(n)=2n^2+2n+1 s(n)=3n^2+3 O(n^2) O(n^2)

12. Ex: Algoritihm Multiply( A,B,n ) Frequency Count Method { Time Space for(i0;i< n;i ++) n+1 A----n^2 { B-----n^2 For(j=0;j< n;j ++) n*n+1 C-----n^2 { n-----1 C[ i,j ]=0; n*n i -----1 for(k=0;k< n;k ++) n*n*n+1 j----1 { k----1 C[ i,j ]=C[ i,j ]+A[ i,k ]*B[ k,j ]; n*n*n s(n)=3n^2+4 } f(n)=2n^3+3n^2+2n+1 O(n^2) } O(n^3) } }