1.2 Algorithm

1.2 Algorithm-Definition and characteristics

Definition: An algorithm is a finite set of instructions which, if followed, accomplish a particular task. An algorithm is a finite sequence of instructions, each of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time. No matter what the input values may be, an algorithm terminates after executing a finite number of instructions.

In addition, every algorithm must satisfy the following criteria:

1. Input:    there are zero or more quantities which are externally supplied;

2. Output:  at least one quantity is produced;

3. Definiteness: each instruction must be clear and unambiguous;

4. Finiteness: if we trace out the instructions of an algorithm, then for all cases the algorithm will terminate after a finite number of steps.

5. Effectiveness: every instruction must be sufficiently basic that it can in principle be carried out by a person using only pencil and paper. It is not enough that each operation be definite, but it must also be feasible.

• Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.
• In formal computer science, one distinguishes between an algorithm, and a program. A program does not necessarily satisfy the fourth condition. One important example of such a program for a computer is its operating system, which never terminates (except for system crashes) but continues in a wait loop until more jobs are entered.
• We represent an algorithm using pseudo language that is a combination of the constructs of a programming language together with informal English statements.

Algorithm Analysis:

• In theoretical analysis of algorithms, it is common to estimate their complexity in the asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input.
• Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimation for the required resources of an algorithm to solve a specific computational problem. Most algorithms are designed to work with inputs of arbitrary length. Analysis of algorithms is the determination of the amount of time and space resources required to execute it.
• Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps, known as time complexity, or volume of memory, known as space complexity.

The Need for Analysis

• The need for analysis of algorithms and how to choose a better algorithm for a particular problem as one computational problem can be solved by different algorithms.
• By considering an algorithm for a specific problem, we can begin to develop pattern recognition so that similar types of problems can be solved by the help of this algorithm.
• Algorithms are often quite different from one another, though the objective of these algorithms are the same.

For example, we know that a set of numbers can be sorted using different algorithms. Number of comparisons performed by one algorithm may vary with others for the same input.

• Hence, time complexity of those algorithms may differ. At the same time, we need to calculate the memory space required by each algorithm.
• Analysis of algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and size required (the size of memory for storage while implementation). However, the main concern of analysis of algorithms is the required time or performance.
• Generally, we perform the following types of analysis −  

1. Worst-case − The maximum number of steps taken on any instance of size a. 
2. Best-case − The minimum number of steps taken on any instance of size a. 
3. Average case − An average number of steps taken on any instance of size a.

• To solve a problem, we need to consider time as well as space complexity as the program may run on a system where memory is limited but adequate space is available or may be vice-versa. In this context, if we compare bubble sort and merge sort. Bubble sort does not require additional memory, but merge sort requires additional space. Though time complexity of bubble sort is higher compared to merge sort, we may need to apply bubble sort if the program needs to run in an environment, where memory is very limited.

Performance of a program:

• The performance of a program is the amount of computer memory and time needed to run a program. We use two approaches to determine the performance of a program. One is analytical, and the other experimental. In performance analysis we use analytical methods, while in performance measurement we conduct experiments.