Introduction to Analysis of Algorithms

Introduction to Analysis of Algorithms

• The efficiency of an algorithm can be decided by measuring the performance of an algorithm. We can measure the performance of an algorithm by computing two factors.

1. Amount of time required by an algorithm to execute.

2. Amount of storage required by an algorithm.

• This is popularly known as time complexity and space complexity of an algorithm.

1. Space Complexity

• The space complexity can be defined as amount of memory required by an algorithm to run.

• To compute the space complexity we use two factors : Constant and instance characteristics. The space requirement S(p) can be given as :

S(p) = C + Sp

where C is a constant i.e. fixed part and it denotes the space of inputs and outputs. This space is an amount of space taken by instruction, variables and identifiers. And Sp is a space dependent upon instance characteristics. This is a variable part whose space requirement depends on particular problem instance.

• Consider three examples of algorithms to compute the space complexity.

Example: 1

Algorithm Add (a,b,c)

//Problem Description: This algorithm computes the addition

//of three elements

//Input: a,b, and c are of floating type

//Output: The addition is returned

return a+b+c

The space requirement for algorithm given in Example 1 is

S(p)=C

Ө  (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[i]

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 requires atleast 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. 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 time complexity is therefore given in terms of frequency count.

Frequency count is a count denoting number of times of execution of statement.

For example

• If we write a code for calculating sum of n numbers in an array then we can find its time complexity using frequency count. This frequency count denotes how many times the particular statement is executed.

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

{

    sum = sum+a[i];

}

Thus we get frequency count to be 3n+2. The time complexity is normally denoted in terms of Oh notation (O). Hence if we neglect the constants then we get the time complexity to be O (n)

Another example

prad will ins &

 Let us consider another example. The following code is typically used to perform matrix addition.

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

{

    for(j=0; j<n; j++)

    {

        c[i][j] = a[i][j]+b[i][j]

    }

}

The frequency count can be computed as follows.

• i = 0 executes once           Frequency count = 1

• i < n executes for n+1 times.

• i + + executes for n times.

Hence frequency count is = 3n²+4n+2

If the constants are neglected then the time complexity will be O(n²).