Introduction
Analysis of Algorithm is the area of computer science that provides tools to analyse the efficiency of different methods of solutions.
The term Algorithm was introduce by the Persian mathematician Al-Khowarizmi in the ninth century. The algorithm is a set of rules which are use to solve real life problems. The algorithm provides a loose form of a solution in a pseudo-programming language.
The first ever algorithm was develop by Babylonians for factorization of a number and to find roots of the equation. Euclid had proposed a famous algorithm for finding greatest common divisor (GCD) of two numbers. We can treat an algorithm as a set of finite instructions.
What is an Algorithm?
If the Algorithm is correct, then the program should produce correct output on valid input. Otherwise it will generate an appropriate error message.
The Algorithm is a set of rules define in specific order to do certain computation and carry out some predefined task. It is a step by step procedure to solve the problem.
Properties in Analysis of Algorithm
A good algorithm have following properties:
(1) Input : Algorithm may take zero or more input arguments. Depending on the problem, the input may be Scalar, Vector, Array, Tree, Graph or some other data structures.
(2) Output : Algorithm reads input, processes it and produces at least one output. Depending on the problem being solve, the output may of the form scalar, vector, array, tree, graph or some other data structures.
(3) Definiteness : All instructions in algorithm should be unambiguous and simple to interpret. There should not be multiple ways to interpret the same instruction. Instructions should be precise and concise.
(4) Finiteness : Every algorithm must terminate after a finite number of steps. If algorithm contains a loop, the upper bound of the loop must be finite. Recursive calls should have a well-define base case to terminate the algorithm.
(5) Effectiveness : The algorithm should be written with a basic set of instructions. The operations should be basic enough to perform exactly using basic set, just like one can perform them with pen and paper. Complex operations should be perform using a combination of basic instruction.
Efficiency in Analysis of Algorithm
The algorithm should be efficient. It should consider all the possible cases of the input set. It should take less space in memory and also require less time for giving the output. The various parameters require to be consider for the efficiency of an algorithm are as follows:
(1) Space Complexity (Efficiency)
It is very important that the algorithm implemented should be such that it requires less memory space. The space complexity can be define as the memory space required for an algorithm to be executed.
The space require in memory for an algorithm to be execute can be Categorize into two parts, viz. Constant(C) and Instance(Sp). The Constant space is require for storing the variables, program etc. The Instance space is require depending on the problem case. Thus the space require S(p) for implementing an algorithm can be given as:
S(p) = C + Sp
The parameter C in the equation is a fix term that depends on the variables require to be declare in the algorithms. This term also includes the space require to store the program or the instructions of the program use to implement the algorithm.
(2) Time Complexity (Efficiency)
The Time Complexity of an algorithm is the time require by the computer to execute the program implemented according to the corresponding algorithm. The calculation of time require to execute the program is slightly complicate and difficult as the time require to execute the program depends on various other parameters besides the algorithm implementation.
Instruction set use, other programs running in the computer, hardware or processor speed, etc. are different parameters on which the execution time depends.
(1) Worst Case Condition (Big O notation) : Depends upon the input, the time require to execute the program for the given algorithm keeps on changing. In Worst Case Condition, the input requires maximum time for execution and the notation use for this case is Big O notation.
(2) Average Case Condition (θ notation) : The Average Case Condition is when the time require to execute the implementation of the algorithm is average. The Notation we use for Average Case Condition is Theta (θ).
(3) Best Case Condition (Ω notation) : The Best Case Condition is when the time require to execute the implementation of the algorithm is best. The notation we use for Best Case Condition is Omega (Ω).
