Algorithm: An Algorithm is a mechanism to manipulate data in data structure.
1. It is a step-by-step method of solving a problem or making decisions, as in making a diagnosis.
2. An established mechanical procedure for solving certain mathematical problems.
An algorithm is just the outline or idea behind a program. We express algorithms in pseudo-code: something resembling C or C++, but with some statements in English rather than within the programming language. It is expected that one could translate each pseudo-code statement to a small number of lines of actual code, easily and mechanically.
Properities of the Algorithm:
1) Finiteness: - an algorithm terminates after a finite numbers of steps.
2) Definiteness: - each step in algorithm is unambiguous. This means that the action specified by the step cannot be interpreted (explain the meaning of) in multiple ways & can be performed without any confusion.
3) Input:- an algorithm accepts zero or more inputs
4) Output:- it produces at least one output.
5) Effectiveness:- it consists of basic instructions that are realizable. This means that the instructions can be performed by using the given inputs in a finite amount of time
To compare the efficiency of algorithms, a measure of the degree of difficulty of an algorithm called Computational Complexity is developed.
Efficiency of an algorithm: the task of determine the computing time and storage space required of an algorithm is known as efficiency of an algorithm or performance analysis.
Two kind of efficiency:
Space Efficiency: The amount of temporary required for running the algorithm, it has two components.
Fixed static part: space for numbers, constants size of input and output Cp Fixed static part.
Variable dynamic part: variables whose size is dependent problem, Sp space required for variable dynamic part.
A total space requirement for an algorithm is the sum of both fixed and dynamic part.
Find sum of two integer numbers.
sum = x+y;
In this code no variable dynamic part space for each integer variable is 4 byte.
We have 3 integer variable and space needed for x,y and sum = 12 bytes.
S(P)= 12 + 0 = 12
Find sum of array elements.
int add(int x, int n)
int total = 0, i;
for(i=0; itotal = total + x[i];
S(P)= 4 X 4 + n = 16 + n
Time Efficiency: the amount of time to run the program is known as time efficiency or time complexity.
Total time taken by an algorithm is the sum of compile time and runtime.
a = a * b
1 unit of time.
for( i=0; ia = i + a;
n unit of time.
for( i=0; ifor( j=0; ja = i + j;
1 unit of time.
Big O: Big O is a technique for comparing two or more algorithm.
Comparison of algorithms without hardware consideration.
Simplification of equation of ease comparison.
Worst-case, Best-case and Average-case Efficiencies:
Let us the complexity function T(n) for certain cases.
Worst case: It gives the maximum value of T(n) for any possible input.
Best case: It gives the minimum value of T(n) for any possible input.
Average case: It gives the expected value of T(n)