What is Algorithm?Analysis of Algorithms by Big O Notation-by enggfact

What is Algorithm?

An algorithm is the procedure having well defined steps for solving a particular problem.The data stored in the data structures is manipulated by using different algorithms,so the study of data structures includes the study of algorithms.Some of the important and most used algorithms are as follows-

1. Greedy algorithm
2. Divide and conquer algorithm
3. Backtracking
4. Randomized algorithms

-Analysis of Algorithms-

There may be many algorithms for solving same problem so it is crucial step to examine which one algorithm is much easier and optimum for the given output of the program and takes less time for the execution of the program.Algorithms are generally analyzed on their time and space requirements.

                                                                                                                                                           One way of comparing algorithms is to compare exact running time of all algorithms.But we all know that the running time is dependent on the language as well as machine used for implementing the algorithm.Even if the machine and language are kept same but calculation of exact time would be very difficult as it would require a lot of time.

                                                                        The running time generally depends on the size of input,for example any sorting algorithm will take less time to sort 10 elements and more time to sort 10,000 elements.So time efficiency is generally expressed in the terms of size of input.

                                                                                                                                         If the size of inputs is n then f(n) which is the function of n denotes the time complexity.Thus to compare two algorithm firstly we have to find out their function in terms of n and then compare the rate of growth of these two functions.It is important to compare the rate of growth of algorithms because some algorithms take less time for less elements but more time for more elements.

                                                                                                                          For finding functions we have to only consider some key operations in the algorithm which account for most of the running time.Other operations are not counted as they take very little time as compared to these key operations and not executed more often than the key operations.For example-in searching we may count the number of comparisons only and in the sorting we may consider the number of swapping in addition to comparisons.We are interested only in the growth rate of the functions so the exact time comparison of f(n) is not necessary.

                                                        Let us consider an example where time complexity is given by the following function-

f(n)=5n2+6n+12

if n=10

% of running time due to the term 5n2 : (500/(500+60+12))*100=87.41%

% of running time due to the term 6n   : (60/(500+60+12))*100=10.49%

% of running time due to the term 12   : (12/(500+60+12))*100=2.09%

                                                                                                                Followinf table shows the growth rate of the following function-

f(n)=5n2+6n+12

n                  5n2               6n               12

1                  21.74%         26.09%      52.17%

10                87.41%         10.49%      2.09%

100              98.79%         1.19%        0.02%

1,000           99.88%         0.12%        0.0002%

10,000         99.99%         0.01%        2.4 E-06%

As we can see that as n grows,the dominant term n2 accounts for most of the running time and we can ignore the smaller terms.Calculating exact function f(n) for the time complexity may be difficult.So the terms which do not significantly change the magnitude of the function can be dropped from the function.In this we can get the approximate time efficiency.This approximate measure of complexity is known as asymptotic complexity.

-Big O Notation-

It is the most commonly used notation to measure the performance of any algorithm by defining its order of growth.If f(n) and g(n) are two functions defined for positive integers,then f(n) is O(g(n)) (read as f(n) is big O of g(n)) if there exist constants c and n such that-

f(n)<=cg(n) for all m>=n

this implies that f(n) does not grow faster than g(n) or g(n) is the upper bound of f(n).

Now let us see how to calculate the O notation from a given function f(n).Since constants don't matter in the O notation,the coefficients of all the terms are set to one.After that we reject all the smaller terms and keep the largest one.the order of terms from smaller to largest is as follows-

O(1),O(log n),O(n),O(n log n),O(n2),O(n3),........O(nk),O(2n),O(3n),....,O(Kn),O(n!)

for example-

f(n)=log n + n! + 5n

remove all the coefficients we have-

log n + n! + n

now from the table it is clear that n! is the largest one so we have to remove log n and 5n from the function and say that f(n)=O(n!).