Algorithm & Asymptotic Notations

First Blog at Hashnode!!!

An algorithm can be defined as the set of finite well defined instructions in order to solve a specific problem.

Understand algorithm with the help of a cooking recipe example.

To cook something new, you need to check the recipe and follow the instructions step wise in order to cook a delicious dish.

Algorithms can be that recipe for programs in programming.

Characteristics of Algorithm:

Finite input and output, Efficient, Language Independent, Feasible, Clear and Unambiguous

Need of Algorithm?

Algorithm helps us to understand the problem well and create a mind map for the solution. It helps finding an good approach to the problem and improve the efficiency of the program. Hence it is very important to understand the Algorithms.

Constructing an algorithm requires some kind of pre information and then by following specific steps we can create algorithm.

Example: Design an algorithm for adding two integers. Steps: 1. START

1. Declare two integer variables num1,num2
2. Take input for the integers
3. Declare sum variable to store the result of sum of num1 and num2
4. Add the integers
5. Print the sum
6. End

Test the algorithm using any programming language Difference between Pseudocode and Algorithm:

An algorithm is the problem solving process but pseudocode is a way of writing algorithms. Pseudocodes are written in informal English which can be easily converted to programming language. But it does not depict the design and there can be errors while transformation of the code.

Analysis of Algorithm Analysis of algorithm is done in order to increase the efficiency of the algorithms by comparing and analysing. Consider we have two algorithms for a single problem, so these to compared and analysed for the best algorithm. Analysis of algorithms is done on the basis of these two fundamental parameters:

1. Space Complexity: The amount of space required by an algorithm to run.
2. Time Complexity : The amount of time needed by an algorithm to run.

There are three types of analysis:

1. Worst Case : Function defined by the maximum amount of time needed by an algorithm for an input of size n.

2. Average Case: Function defined by the average number of steps taken.

3. Best Case: Function defined by the minimum number of steps taken of any instance of size 'n'.

Asymptotic Notations These notations describes the algorithm efficiency and performance in a meaningful way. They describe the behaviour of time and space complexity for large instance characteristics.

Consider two functions 'f' and 'g'. These functions are from N to R, then :

Ω(g) : functions that grow at least as fast as g

Θ(g) : functions that grow at the same rate as g

О(g) : functions that grow no faster than g

Let us look to them in detail:

Big oh Notation (О) : The upper bound for the function 'f' is provided by the Big oh Notation.

The function f(n)=О(g(n)), iff there exists positive constants c and No. such that f(n)<=c*g(n) Ɐ n>=No

Example :

f(n)=2n+3 2n+3<=2n+3n 2n+3<=5n

Therefore, f(n)=О(n)

Some common functions used are : constants, logarithmic, linear, quadratic, exponential, factorial and cubic.

NOTE: When f(n) is polynomial of n, then order of f(n) i.e. the g(n) is f(n)=О(g(n))

Big Omega Notation(Ω):

The lower bound for the function (f) is provided by the big omega notation(Ω).

The function f(n)=Ω(g(n)) iff there exists positive constants c and No. such that f(n)>=c * g(n) Ɐ n>=No.

Example: f(n)=3n+5 3n<3n+5, Ɐ 'n' {c=3} thus, f(n)= Ω(n)

Ω(g(n)) = { f(n) : There exist positive constant c and n0 such that 0 ≤ c g(n) ≤ f(n), for all n ≥ n0}

Big-Theta Notation(θ) :

The lower and upper bound for the function 'f' is provided by the big theta notation(θ).

The function f(n) = θ(g(n)) iff there exists C1, C2 and n0. such that C1g(n) <= f(n) <= C2g(n)

Θ(g(n)) = {f(n) : There exist positive constant c1, c2 and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n), for all n ≥ n0}

Example:

Asymptotic Notation Properties:

1. Reflexivity

f(n)= Θ(n) f(n)= Ω(n) f(n)= О(n)

2. Symmetric and Transpose Symmetry

f(n)= Θ(n) iff g(n)= Θ(f(n)) f(n)= Ω(n) iff g(n)= Ω(f(n)) f(n)= o(n) iff g(n)= ω(f(n))

3. Transitivity

f(n)= Θ(n) and g(n)= Θ(h(n)) imply f(n)= Θ(h(n)) f(n)= Ω(n) and g(n)= Ω(h(n)) imply f(n)= Ω(h(n)) f(n)= o(n) and g(n)= o(h(n)) imply o(n)= o(h(n))

Order of growth functions:

factorial>exponential>polynomial>logarithmic>constant

The growth of functions is directly related to the complexity of algorithms. The algorithm efficiency and performance in comparison to alternate algorithm is best described by the order of growth of the running time of an algorithm.

Asymptotic Notations allow the comparisons of the performances of various algorithms. It is a way of comparing functions.