What is An Algorithm?
An algorithm is a sequence of unambiguous instructions which can be used to solve the problem . 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.
Practical Algorithm design issues:
There are some Criteria that we need to take care while designing the algorithm for any process:
1. Try to save time (Time complexity).
2. Try to save space (Space complexity).
3. 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.
Performance of a program:
The Performance of a program is nothing but the amount of computer memory it consumed and the the time required to execute the program, There are some methods to determine the performance of a program, Analytical method and the other one is Experiment method
In performance analysis we use analytical methods, while in performance measurement we conduct experiments.
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
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:
1.Instruction space: Instruction space is the space needed to store the compiled version of the program instructions.
2.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.
3.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.
Complexity of Algorithms
The complexity of an algorithm M is the function f(n) which gives the running time and/or storage space requirement of the algorithm in terms of the size ‘n’ of the input data. Mostly, the storage space required by an algorithm is simply a multiple of the data size ‘n’. Complexity shall refer to the running time of the algorithm.
The function f(n), gives the running time of an algorithm, depends not only on the size ‘n’ of the input data but also on the particular data. The complexity function f(n) for certain cases are:
- Best Case : The minimum possible value of f(n) is called the best case.
- Average Case : The expected value of f(n).
- Worst Case : The maximum value of f(n) for any key possible input.