CONTENTS 1. WHAT IS PERFORMANCE ANALYSIS
2. SPACE COMPLEXITY
2.1. components of space complexity
2.2. example
3. TIME COMPLEXITY
3.1. components of time complexity
3.2. operation counts
3.3. best, worst and average operation
counts
3.4. step counts

Slide 3:

Performance Analysis (machine independent)
space complexity: storage requirement
time complexity: computing time
Performance Measurement (machine dependent)

1. WHAT IS PERFORMANCE ANALYSIS :

1. WHAT IS PERFORMANCE ANALYSIS Performance of a program
- amount of computer memory and time needed to run a
program.
Approaches
- two approaches to determine the performance of a program
1. Analytical (or) Performance analysis
- use analytical methods
2. Experimental (or) performance measurement
- its measured by conducting experiments
Space complexity
- is the amount of memory needed to run and completion of a
program.

Slide 5:

Reason for space complexity
(i) program run on multi-computer system
amount of memory allocated to the
program
(ii) for any computer know whether (or) not sufficient
memory
to run the program
(iii) a problem have several possible
different space requirement specify available with

Slide 6:

Example
- one java compiler of your computer need only 1-MB of
memory.
- another need 4.MB of memory
- 1.MB compiler is the only choice, if your computer has less
than 4.MB of memory.
- computer have extra memory will prefer smaller compiler,
even it’s capabilities are comparable to bigger compiler.
(iv) Space complexity is used to estimate the size if the largest
problem, that a problem can solve.

Slide 7:

Time complexity
- amount of computer time needed to run and completion of a
program.
Reason for Time complexity
1. some computer system requires users to provide an upper
limit on the amount of time, the program will run.
- once this upper limit is reached the program is
aborted.
- the solution is:
provide a time limit
2. The program developed user
by
satisfactory real-time
response provide

Slide 8:

Example:
(a) A text editor takes a minute to move the cursor from one
page down (or) up - is acceptable by many users.
(b) A spread sheet program takes several minutes to re-
evaluate the cell in a sheet - is satisfactory by few users.
* (i.e) from the time-complexity of the program module:
- we can decide whether (or) not the response
time will be acceptable.
* if it’s not acceptable then
- redesign the algorithm (or)
- give faster computer to user

2. SPACE COMPLEXITY :

2. SPACE COMPLEXITY 2.1.Components of space complexity
the space needed by a program has following components
(a) Instruction space
(b) Data space
(c) Environment stack space
(a) Instruction space
- is the space needed to store the compiled version of the
program instructions.
- the amount of instruction space needed is depends on
following factors:
(i) the compiler used to compile the program into machine
code.
(ii) the compiler option – at the time of compilation.
(iii) the target of computer.

Slide 10:

- the compiler is a very important factor in determining
- how much space the resulting code needed.
Example:
consider the following formula.
a + b + b * c + ( a + b - c) / ( a + b) + 4
- it’s evaluated in three possible code as follows:
(next slide)
- these codes need a different amount of space & the compiler
determine exactly which code will be generated.
(e.g.)
compiler provide optimization options to users.
1. code-optimization
2. execution-time optimization
- the code in (b) is generated in non-optimization mode
(refer next slide)

Slide 11:

LOAD a LOAD a LOAD a
ADD b ADD b ADD b
STORE t1 STORE t1 STORE t1
LOAD b SUB c SUB c
MULT c DIV t1 DIV t1
STORE t2 STORE t2 STORE t2
LOAD t1 LOAD b LOAD b
ADD t2 MUL c MUL c
STORE t3 STORE t3 ADD t2
LOAD a LOAD t1 ADD t1
ADD b ADD t3 ADD t4
SUB c ADD t2
STORE t4 ADD 4 (c)
LOAD a
ADD b (b)
STORE t5
LOAD t4
DIV t5 where: t1,t2,-----t6
STORE t6 temporary variable needed for space
LOAD t3
ADD t6
ADD 4
(a) program-1

Slide 12:

- the code in (C) is generated in optimization mode & the code is
shorter & time efficient.
- use of optimization mode
-- increase the time needed to compile the program
- the configuration of the target computer affect the size of
compiled code.
(b) Data Space
1. Data space is the space needed to store all constant &
variable values.
2. components of data space
(a) space needed by constant and simple variables
(b) space needed by dynamically allocated objects
(e.g) Arrays , class

Slide 13:

3. java language specifies the space allocated for simple variables and constants.
(e.g) space requirement of an array is calculated as follows:
= array size * space needed for a single array element
double[ ] a = new double[ 100 ]
int[ ] [ ] maze = new int[rows] [ cols]
=> when computing the space allocated to an array ignore
calculating space allocated to store array size & type.
double[ ] a = new double[100];
the array ‘a’ has space for 100 elements of type double
[1-byte = 8-bits]
i.e. 100 * 8 = 800 bytes

Slide 14:

int[ ] [ ] maze = new int [rows] [cols]
i.e. total space taken by this array = 4 * rows * cols (bytes)
(C) Environment stack
- it save the information which is needed to resume the
execution of partially completed methods.
- when each time a method is invoked the following data
are saved on the environment stack.
(i) return address
(ii) values of all local variables & formal parameter
in the method are invoked.

3. TIME COMPLEXITY :

3. TIME COMPLEXITY 3.1. components of time complexity
1. Time complexity of a program depends on:
“all the factors that the space complexity depends on”
2. some computer run a program faster & execute 109
instructions/sec, but some computer executes 107
instruction/sec.
(e.g.)
In program-1, program (c) requires less execution time
than the program (a).
3. some compiler take less time than others to generate
computer code.
4. smaller problem generally take time than larger problem.
5. Time taken by a
program = sum (compiler time & run time (or)
execution time)

Slide 16:

6. Compiled program can run several times without re-compilation.
7. The runtime is denoted as tp (instance characteristic)
8. If we know the characteristic of a compiler we can determine the number of addition, subtraction, multiplication, division , compares, loads, stores etc.,
Formula for tp:
tp (n) = CaADD(n) + CsSUB(n) + CmMUL(n) + CdDIV(n) + ……..
Where:
n - instance characteristics
Ca
Cs - time needed for addition, subtraction, division,
Cm multiplication
Cd
ADD,SUB, - functions
MUL, DIV

Slide 17:

9. Two approaches to estimate Run-time of a program are:
(a) identify one (or) more key operations and determine
number of times the operation performed.
(b) determine total number of steps executed by the
program.
3.2. operation counts
1. One way to estimate the time complexity of a program (or)
method select one (or) more operations – such as “add,
multiply, compare”, and determine how many of each is done.
2. The success of this method is depends on:
- ability to identify the operations, that contribute to the
time complexity.
3. Examples:
(a) max element
- find out the largest element in an array a[0:n]

Line-4
Line-5
Line-6
=> one way to rearrange the elements in an array ‘a’ is
a[0] <= a[1] <= ………..<= a[a.length-1]
=> n = a. length
determine the largest elements in ‘n’ & move it to a[n-1].
determine the next largest element in remaining n-1 element
& move it to a[n-2]. 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5

Slide 20:

=> from the example:
a[0:5] = [6, 5, 8, 4, 3, 1] is sorted into
a[0:5] = [1, 3, 4, 5, 6, 8]
=> Java coding
public static void selectionsort (comparable[] a)
{
for(int size = a.length; size > 1; size--)
{
// find max object in a[0:size-1]
int j = mymath.max(a,size-1);
//move max object to right end
mymath.swap (a, j, size-1);
}
}

3.3. best, worst and average operation counts :

3.3. best, worst and average operation counts Average case
refer to running time of an algorithm as an average taken over
all inputs of the same size.
Worst case
refer to running time of an algorithm as the maximum taken
over all inputs of the same size.
Best case
refer to running time of an algorithm as the minimum taken
over all inputs of the same size.

Slide 22:

Graphical description
A B C D E F G
input instance Running
Time Worst case
time best case
time 6
5
4
3
2
1 Average case
time

Slide 23:

Examples:
(a) sequential search
(b) Insertion into a sorted array
(c) Rank sort Revisited
(d) Selection sort Revisited
(e) Bubble sort Revisited
(f) Insertion sort
(b) Insertion into a sorted Array
1. Insert a new element into a array & the result is a also
sorted array.
a[0:4] =[2,4,6,8,9]
2. Insert ‘3’ into above array a[0:4] & the result is a[0:5]=
a[2,3,4,6,8,9]. 0 1 2 3 4

Slide 24:

3.The insertion may be done by beginning at the right end & successively moving one position right, to find the location for new element.
4. In our (e.g) we moved 9,8,6& 4 to insert the element 3.
Line-1
Line-2
Line-3
Lline-4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 5 5 5 5

Slide 25:

Line-5
Line-6
5. The best (or) minimum no. of comparison is 1. It happen, when the new element ‘x’ is inserted at right end.
6. The maximum no. of comparison is ‘n’. It happens when ‘x’ is inserted at left end.
7. The average count is
1/n+1 ( ∑ (n-i) + n) = 1/n+1 ( ∑ j + n) 0 1 2 3 4 5 0 1 2 3 4 5 n-1 i=0 j=1 n

Slide 26:

8. Java coding
public static void insert (comparable [ ]a, int n, comparable x)
{
if( a . length < n + 1)
throw new illegalArgumentException (“array not large enough”);
//find proper place for x
int i;
for( i=n-1; i>=0 && x . compareTo a[i]) < 0; i--)
a[i+1] = a[i];
a[i+1] = x; // insert x
}

Step Count :

Step Count Methods To Compute The Step
Count
Introduce variable count into programs
Tabular method
Determine the total number of steps contributed by each statementstep per execution frequency
add up the contribution of all statements

3.4. step counts :

3.4. step counts Step count
- is a function of the instance characteristics
Step
- any computation unit that’s independent of the selected
characteristics.
(e.g) 100 – multiplications may be one step,
10 – additions may be one step
but ‘n’ – additions,
where : ‘n’ – is an instance characteristics
Program Step
A program step is a syntactically or semantically meaningful program segment whose execution time is independent of the instance characteristics.

Slide 29:

Example:
abc = a + b + b * c + (a + b - c) / (a + b) + 4
the amount of computing represented by one program step may be different from another program step representation.
abc = a + b + c
Count
- we can determine the no. of steps a program /method takes to complete its task by creating a global variable ‘count’. Count=0
- next introduce statement into the program to increment ‘count’
- each time the statement is executed,’ count’ is incremented.
(count++).
- the value of the no. of steps taken to terminate the
count = program/method

Slide 30:

Example:
(program without ‘count’ variable)
public static computable sum (computable [ ] a, int n)
{
if (a.length == 0) return null;
computable sum = (computable) a[0].zero();
for ( int I = 0; I < n; i++)
sum.increment (a [i] );
return sum;
}

Slide 31:

Example: (program with ‘count’ variable)
public static computable sum (computable [ ] a, int n)
{
count++; //for conditional and return
if (a.length == 0) return null;
computable sum = (computable) a[0].zero();
count++; // for preceding statement
for ( int I = 0; I < n; i++)
{
count ++; //for the for statement
sum.increment (a [i] );
count++; //for increment
}
count++; //for last execution of for statement
count++; //for return
return sum;
}

Tabular method description of step count :

Tabular method description of step count Instead of introducing ‘count’ variable in the statement, build a table to list the total no. of steps that each statement contributes to ‘count’.
In the table format first determine the
- no. of steps/execution (s/e) of the statement and
- next the total no. of times (i.e.frequency) each statement is
executed.
- next combine above two steps to find out ‘total contribution’
of each statement.
- last step is add the contribution of all statements to obtain
the step count for entire program.
- this overall approaches to obtain a step count is called
“ Profiling”.

Matrix Addition :

Matrix Addition Figure 1.4: Step count table for matrix addition

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

By: karthikarthick (31 month(s) ago)

send soon