LESSON TWO

PERFORMANCE ANALYSIS OF ALGORITHMS

2.1 Introduction

In this lesson we shall focus on evaluating the cost of a given computer algorithm in order to
determine its efficiency in comparison with other algorithms using a common measure to perform
the same task. The cost of an algorithm is measured based on the following: Time taken to run into
completion, the amount of computer memory required in order to hold a code/program under
execution and other required system resources.

The lesson covers:

 Lesson Objectives
 Topic Overview
 Time Complexity
 Space Complexity
 Learning Activities
 Summary
 Further reading.
2.2 Lesson Objectives
By the end of this lesson you should be able to:

1. Analyse a given algorithm and state the following:

o The algorithm’s time complexity.
o The required amount of memory to execute it.
2. State the system resources required to execute an algorithm

2.3 Topic Overview

 The performance analysis is an objective way to evaluate the cost of an algorithm or code
section.

 The goal of performance analysis is to have a conclusive way to compare algorithms based
on a common measure.

 Performance analysis of an algorithm can be done based on the following as shown in the
diagram below.

- Computations of best-case, average-case and worst case

- Measuring input size.
- Computing order of growth.
- Measuring time complexity.
- Measuring time complexity.
  In this, lesson we shall only focus on the following two complexities (time and space)

 The efficiency of an algorithms can be measured during the process of transforming input
objects into output objects. During this process they spend system resources in terms of
running time or storage capacity.

That is:

- Amount of time required by an algorithm to execute into completion

- Amount of storage required by an algorithm

Therefore, they are typically known as

- Time complexity
- Space complexity

2.4 Space Complexity

Space complexity is defined as the amount of memory required by the algorithm to run. It is
computed based on the following two factors (characteristics):

- Constant
- Instance

The space requirement S(p) can be given as:

Where C is a constant denoting the fixed part of inputs and outputs.

The space is taken by:

- Instructions
- Variables and
- Identifiers

While Sp is space dependent by instance characteristics. It’s a variable part whose space
requirements is depends on particular problem instance.

Example 1:

Algoritm Add (a, b, c)

//Problem Description: This algorithm computes the addition

//of three elements a, b and c are of floating type

//Output: The addition is returned

return a+b+c

The space requirement for algorithm given above is

S(p)=C Omega(Sp)=0

If we assume that a, b and c occupy one word size then total size comes to be 3.

Example 2:

Algorithm Add (x, n)

//Problem Description The algorithm performs addition of

//all the elements in an array. Array is of floating type.

//Input: An array x and n is total number of elements in array

//Output: returns sum which is of data type float.

sum 0. 0
for i  1 to n do

sum  sum + x[il

return sum

The space requirement for the above given algorithm is

S(p) >= (n + 3)

the 'n' space required for x[], one unit space for n, one unit for i and one unit for sum

Example 3:

Algorithm Add (x, n)

/ /problem Description: This is a recursive algorithm which

//computes addition of all the elements In an array x[]

//input= x[i] is of floating type, total number of elements in an array

/ /output: returns addition of n elements of an array

return Add (x, n-1) +x[n]

The space requirement is

S(p) >= 3(n + 1)

The internal stack used for recursion includes space for formal parameters, local variables and
return address. The space required by each call to function Add require at least three words (space
for n values + space for return address + Pointer to x[])

The depth of recursion in n+1 (n times call to function and one return call). The recursion stack
space will be >= 3(n+1)

2.5 Time Complexity

The time complexity of an algorithm is the amount of computer time required by an algorithm to
run to completion.
It is difficult to compute the time complexity in terms of physically clocked time. For instance, in
multiuser system, executing time depends on many factors such as:

 System load

 Number of other programs running

 Instruction set used

 Speed of underlying hardware

The running time of an algorithm typically grows with the input size.

Algorithm analysis requires a set of rules to determine how operations are to be counted.
There is no generally accepted set of rules for algorithm analysis.
 In some cases, an exact count of operations is desired; in other cases, a general
approximation is sufficient.
 The following presented rules are typical to those intending to produce an exact count of
operations.
Rules

1. We assume an arbitrary time unit.

2. Execution of one of the following operations takes time 1:

 assignment operation (a=10)

 single I/O operations (scanf, printf)

 single Boolean operations, numeric comparisons (AND, OR, NOT)

 single arithmetic operations (a+b)

 function return (return value)

 array index operations, pointer dereferences (array[0], *ptr- retrieve a data pointed
by it)

3. Characterize performance in terms of key operation(s)

 Sorting: count number of times two values are compared. count number of times
two values are swapped

 Search: count number of times value being searched for is compared to values in
array
  Recursive function: count number of recursive calls

4. Running time of a selection statement (if, switch) is the time for the condition evaluation
+ the maximum of the running times for the individual statements in the selection.

Example (rtime=2)

if (a>b)

a=a+b

else

b=b-a

5. Loop execution time is the sum, over the number of times the loop is executed, of the body
time + time for the loop check and update operations, + time for the loop setup.

Example (rtime=16)

for (i=0; i<5;i++)

a=a+i

6. Running time of a function call is 1 for setup + the time for any parameter calculations +
the time required for the execution of the function body.

How can we say that one algorithm performs better than another one?

• Quantify the resources needed to run it. In terms of:

– Time

– Memory

– I/O, disk access

– Circuit, power, etc.

• Time is not merely CPU clock cycle

– Therefore, algorithms are studied independent of implementations, platforms, and

hardware.

– Hence, an objective point of reference is required.

 – For that case, measure time by the number of operations as a function of the input
size to the algorithm

Input Size

It is observed that if the input size is longer, then usually the algorithms runs longer time

For a given problem, we characterize the input size n appropriately

– Sorting: The number of items to be sorted

– Graphs: The number of vertices and/or edges

– Matrix manipulation: The number of rows and columns

– Numerical operations: the number of bits needed to represent a number

• The choice of an input size greatly depends on the elementary operation: the most relevant
or important operation of an algorithm are.

– Comparisons

– Additions

– Multiplications
2.6 Learning Activities

(i) Describe the time complexity

(ii) Describe space complexity.

2.7 Summary

Efficiency to perform a given computer task depends on two things.

- System computational power.

- Efficiency of an algorithm

Different algorithms consume different amount of system resources in terms of time, space,
I/O, disk access or power. Their performance analysis in terms of how much system resources
they consume to execute a given tasks provides an opportunity to choose the most efficient
algorithm for the said task.
2.8 Further Reading

1. Click, P. (2004). Administration of programmes for young children. NY: Thomson Delmar learning.