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:
Input: There are zero or more quantities, which are externally supplied;
Output: At least one quantity is produced;
Definiteness: Each instruction must be clear and unambiguous;
Finiteness: If we trace out the instructions of an algorithm, then for all cases the algorithm will terminate after a finite number of steps;
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.
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.
Practical Algorithm design issues
Choosing an efficient algorithm or data structure is just one part of the design process. Next, will look at some design issues that are broader in scope. There are three basic design goals that we should strive for in a program:
- Try to save time (Time complexity).
- Try to save space (Space complexity).
- Try to have face.
A program that runs faster is a better program, so saving time is an obvious goal. Like wise, a program that saves space over a competing program is considered desirable. We want to “save face” by preventing the program from locking up or generating reams of garbled data.
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.
Time Complexity
The time needed by an algorithm expressed as a function of the size of a problem is called the TIME COMPLEXITY of the algorithm. The time complexity of a program is the amount of
computer time it needs to run to completion.
The limiting behavior of the complexity as size increases is called the asymptotic time
complexity. It is the asymptotic complexity of an algorithm, which ultimately determines the size of problems that can be solved by the algorithm.
Space Complexity:
The space complexity of a program is the amount of memory it needs to run to completion. The space need by a program has the following components:
Instruction space:
Instruction space is the space needed to store the compiled version of the
program instructions.
Data space:
Data space is the space needed to store all constant and variable values. Data
space has two components:
- Space needed by constants and simple variables in program.
- Space needed by dynamically allocated objects such as arrays and class instances.
Environment stack space:
The environment stack is used to save information needed to resume execution of partially completed functions.
Instruction Space:
The amount of instructions space that is needed depends on factors such as:
- The compiler used to complete the program into machine code.
- The compiler options in effect at the time of compilation
- The target computer.
