CHARACTERISTICS OF AN ALGORITHM

Next, we consider the concept of algorithm in more detail. While designing an algorithm as a solution to a given problem, we must take care of the following five important characteristics of an algorithm:



1. Finiteness: An algorithm must terminate after a finite number of steps and further each step must be executable in finite amount of time. In order to establish a sequence of steps as an algorithm, it should be established that it terminates (in finite number of steps) on all allowed inputs.

2. Definiteness(no ambiguity): Each step of an algorithm must be precisely defined; the action to be carried out must be rigorously and unambiguously specified for each case. Through the next example, we show how an instruction may not be definite.

Example 1.4.1: Method which is effective (to be explained later) but not definite.
 The following is a program fragment for the example method:

.....

{in the above, the symbol  denotes that the value on its R.H.S is assigned to the variable on its L.H.S. Detailed discussion under (i) of Section 1.6.1}

All the steps, like tossing the coin etc., can be (effectively) carried out. However, the method is not definite, as two different executions may yield different outputs.

3. Inputs: An algorithm has zero or more, but only finite, number of inputs. Examples of algorithms requiring zero inputs:

(i) Print the largest integer, say MAX, representable in the computer system being used

(ii) Print the ASCII code of each of the letter in the alphabet of the computer system being used.

(iii) Find the sum S of the form 1+2+3+…, where S is the largest integer less than or equal to MAX defined in Example (i) above.

4. Output: An algorithm has one or more outputs. The requirement of at least one output is obviously essential, because, otherwise we can not know the answer/solution provided by the algorithm.

The outputs have specific relation to the inputs, where the relation is defined by the algorithm

5. Effectiveness: An algorithm should be effective. This means that each of the operation to be performed in an algorithm must be sufficiently basic that it can, in principle, be done exactly and in a finite length of time, by a person using pencil and paper. It may be noted that the ‘FINITENESS’ condition is a special case of ‘EFFECTIVENESS’. If a sequence of steps is not finite, then it can not be effective also.

A method may be designed which is a definite sequence of actions but is not finite (and hence not effective)

Example 1.4.2: If the following instruction is a part of an algorithm:
Find exact value of e using the following formula

There are some methods, which are not definite, but still called algorithms viz., Monte Carlo algorithms in particular and probabilistic algorithms in general. However, we restrict our algorithms to those methods which are definite alongwith other four characteristics. In other cases, the full name of the method viz., probabilistic algorithm, is used.

e = 1+ 1/(1!) + 1/(2!) + 1/(3!) +…..

            and add it to x.

Then, the algorithm is not effective, because as per instruction, computation of e requires computation of infinitely many terms of the form 1/n! for n = 1, 2, 3, ….., which is not possible/effective.

However, the instruction is definite as it is easily seen that computation of each of the term 1/n! is definite (at least for a given machine)

.Ex. 2) For each of the following, give one example of a method, which is not an algorithm, because
(i) the method is not finite
(ii) the method is not definite
(iii) the method is not effective but finite.