2 Analysis of Iterative Algorithms

S. Sridhar

Module 4

Analysis of Iterative Algorithms

 

Algorithm analysis is necessary to determine the efficiency of an algorithm and to decide the efficiency of the given algorithm. The learning objectives of this module

  • To understand the process of algorithm analysis
  • To know the types of analysis
  • To understand the concept of step count
  • To understand the concept of Operation count

Algorithmic Complexity theory is a field of algorithm that deals with the analysis of algorithms in terms of computational resources and its optimization. An efficient algorithm is the one that uses lesser computer resources such as time and memory.

 

Analysis of algorithms is important for two reasons

1.  To estimate the efficiency of the given algorithm

2.  To find a framework for comparing the algorithms or solutions for the given problem.

 

But the analysis of an algorithm is not easy as analysis is dependent on many factors such as speed of machine, programming language, efficiency of language translators, program size, data structures used, algorithm design style, ease of its implementation, understandability and its simplicity.

 

Hence, analysis focus on two aspects – subjective measures and objective measures.

  1. Subjective measures: Subjective measures are algorithm design style, ease of its implementation, understandability and its simplicity. For example, two algorithms can be compared based on ease of implementation. But, the subjective measures differ from person to person and time to time. Hence, to compare algorithms some objective measures or metrics are required.
  2. Objective measures: Objective measures are measures like running time, memory space, disk usage and network usage.

Out of all objective measures, time complexity and space complexity are important.

 

Time complexity: Time complexity measures are very popular. Time efficiency or time complexity means how much run time an algorithm takes for execution for the scaled input. It expresses the complexity as some measure of input size and thus predicts the behavior of the given algorithm. By time, the run time is referred as compilation time is not important. Also the unit of running time is in terms of CPU cycle.

 

Let us recollect some of the important concepts for algorithm analysis.

  1. Instance: All valid inputs are called instances of the given algorithm.
  2. Domain: All the valid inputs form a domain
  3. Input size: Input size is the length of the input. Often, logarithm is also used to represent the size of the input to keep the number small as the logarithm of a number is often very small compared to the number itself. For example, the input size of the sorting program is N, if sorting involves N numbers. It can be noted that complexity is thus directly dependent on input size as sorting of 10 numbers is easy. But on the other hand, sorting of million numbers is a complex task.

Thus complexity is expressed as a function of input size, T(n) , where ‘n’ is the input size. T(n) can be estimated using two types of analysis.

  1. Apriori (or Mathematical analysis)
  2. Posteriori (or Empirical analysis).

Apriori analysis (or Mathematical analysis) is done before the algorithm is translated to a program. The step count or the number of executed count of the dominant operations is used to  estimate the running time. On the other hand, posteriori analysis is done by executing the program using standard datasets to estimate time and space.The apriori (or Mathematical) algorithm analysis is framework involves following tasks:

  1. Measuring the input size of the algorithm.
  2. Measuring the running time using either step count or count of basic operations.
  3. Find the worst-case, best-case and average case efficiency of the algorithm as it is often naïve to think that for all kinds of inputs, the algorithm work uniformly.
  4. Identify the rate of growth. This step determines the performance of the algorithm when the input size is increased.

Let us discuss now about step count and operations count.

 

Step count

T(n) is obtained using the step count of the instructions. The idea is based on the fact that the algorithm is basically a set of instructions. So the run time is dependent of the count of elementary instructions or program steps. Step count is the count of syntactically and semantically meaningful instruction and thus time complexity is expressed as a measure of step count.

 

Operation Count

Another popular school represented by Donald E Knuth prefer the determination of running time based on the count of basic operations. The idea is to use dominant operator and expressing the complexity as the number of times the basic (or dominant) operator is executed.

 

Let us discuss about some examples of step count. The idea is to count the instructions that are used by the given algorithm to perform the given task. The idea is to find the step count (called steps per execution s/e) of each instruction. Frequency is the number of times the instruction is executed. The total count can be obtained by multiplying the frequency and steps per execution. The s/e is not always 1. If a function is invoked, then s/e is dependent on the size of the function.

Let us discuss about some examples.

 

Example 1

Consider the following program segment as shown in Table 1.

 

Table 1: Step count of swap of two variables

S.No. Program s/e Frequency Total
1 Algorithm Interchange(x,y) 0 – –
2 Begin 0 – –
3 temp = x; 1 1 1
4 y = x; 1 1 1
5 y = temp 1 1 1
6  

End

 0    
– –
  Total     3

The step count of instructions 1, 2 and 6 are zero as these are not executable statements. By this it is meant that the computer system need not execute these statements. The executable statements are 3, 4 and 5. It can be observed that the total is calculated based on the multiplication of s/e and frequency. So T(n) = 3. This means the algorithm computes a fixed number of computations irrespective of the algorithm input size and hence the behaviour of this algorithm is constant.

Example 2

Consider the following algorithm segment as shown in Table 3.3:

 

Table 3: Step count of doubling of numbers

SNo. Program s/e Frequency Total
1 Algorithm Sum(A,n) 0 – 0
2 Begin 0 – 0
3 Sum = 0.0 1 1 1
4 For i = 1 to n do 1 n+1 n+1
5 Sum = sum + A[i] 1 n n
6 End for 0 – 0
7 Return Sum 1 1 1
8 End 0 – –
Total 2n+3

Here, the instructions 1, 2 and 6 are non-executable. Statement 4 has frequency of n+1. This is because additional iteration is required for control to come out of the for-loop. The statements 5 and 6 are within the for-loop. So they are executed ‘n’ times. So the count of these instructions is n. It can be observed that the total count is obtained by multiplying the s/e and the frequency. Thus it can be seen that T (n ) = 3n + 3 is the time complexity function of this algorithm segment.

Second Philosophy: Count of Basic Operations

As said earlier, the idea is to count all the operations like add, sub, multiplication and division. Some of the operations that are typically used are assignment operations, Comparison operations, Arithmetic operations and logical operations. The time complexity is then given as the number of repetitions of the basic operation as a function of input size. Thus the procedure for function op count is given as follows:

  1. Count the basic operations of the program and express it as a formula
  2. Simplify it
  3. Represent the complexity as a function of count.

The rules for finding the basic operation count for some of the control constructs are given as follows:

 

1. Sequence

Let us consider the following algorithm segment

 

Begin

s1

s2

End

 

If statement s1 requires m operations and statement s2 requires n operations. Then the whole algorithm segment requires m+n operations. This is called addition principle. For example for the algorithm segment

 

index = index + 1

sum = sum + index

By addition principle, if C1 is the count of first instruction and C2 is the count of second instruction, the count of the algorithm segment is C1 + C2.

 

2. Decision

For the decision structure, the rule is given below:

IF (Condition C) Then Statement P

Else

Statement Q

The time complexity of this program segment is given as T(n) = Maximum { TP, TQ}. For example, the following algorithm segment

if (n < 0) then

absn = -n

else

absn = n

The op count is C1 + max (C2, C3) as C1 is the count of the condition. C2 and C3 are the op counts of the remaining instruction. Thus, the maximum operations of either if part or else part is taken as the time complexity.

 

3. Repetition

The time complexity of the algorithm for loops is given as

 

T ( n) » n ´TR

Thus a statement s1 that requires m operations, is executed ‘n’ times in a loop, and then the program segment requires m X n operations. This is called multiplication principle.

 

Thus for the following algorithm segment 

Instruction cost Frequency
i = 0 c1 1
sum = 0 c2 1
while (i <=n) c3 n+1
i = i + 1 c4 n
sum = sum + i c5 n

The total cost is given as         c1 + c2 + n c3 + c3 + n c4 + n c5

= c1 + c2 + c3 + n(c3+c4+c5).

 

This is the complexity analysis of the above algorithm.

 

Summary

Thus this module can be summarized as follows.

  1. Algorithm efficiency is important for algorithm analysis.
  2. Two types of analysis are – apriori (or Mathematical analysis) and Posterior (or Empirical analysis)
  3. Time complexity can be estimated using step count or operation count.

Supporting & Reference Materials

  • Sridhar S, Design and Analysis of Algorithms, Oxford University Press, 2014.
  • Cormen, T.H., C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992
  • Horowitz and Sahni, Fundamental Algorithms, Universities Press, New Delhi, 2000
  • Aho,A.V., J.E.Hopcroft and J.D. Ullman, The Design and analysis of algorithms, Addison-Wesley, Reading, MA, 1974
  • Dromey, R,G., How to solve it by Computer, Prentice-Hall, Englewood cliffs, NJ, 1982