Analysis Design Of Algorithm (ADA) | Introduction

📌Highlights: Hi friends in this post, I am  going to explain  about introduction of Analysis Design Of Algorithm (ADA). We must know about , What is analysis ? What is design ? What is algorithm ? What is problems and how we solve it ?, We also discuss about design strategy and Asymptotic Notations such as Big-oh notation, Big-omega notation, Theta notation, Little-oh notation, Little-omega notation, Incremental and divide and conquer approach.

In Analysis Design Of Algorithm, we study how to analyse and design any algorithm for solving any problem. It consist of three main keywords such as :

1. Analysis 

2. Design 

 3. Algorithm

Let we discuss about each key`word in details.

Analysis : 

Analysis of algorithm tells about the performance of algorithm.We can check the performance of any algorithms by using two parameters such as SPACE and TIME. We will discuss in detail about these parameters. 

There are following parameter checking algorithm.

1. Space

2. Time 

Space- Space tells how mush space is required  in memory to solve any problem.

Time- Time tells how much time (execution time) is taken by algorithm to solve any problem.

Analysing Algorithm: It is categorise into two such as

1.Space Complexity: The amount of space required by an algorithm or program is called as space complexity and it is depend on Input size (n).

2.Time Complexity: The amount of time or program in its complete execution is called time complexity and generally it is denoted by T(n) which also depend on input size(n).

Design:

Algorithm is design to solve any problem. It is a set of steps to solve any problem.

For design any algorithm, we have following questions in our mind such as:

1.How to design algorithm ? (such as dynamic programming, Greedy method, Back tracking, Branch and Bound etc.)

2.How to validate any algorithms ? ( check algorithm on different input and check their output whether it is correct or not)

3.How to analysis an algorithm? (For analysis we must check how much time is taken for execution of this algorithm and how much space is taken in memory by this algorithm. That is known as time and space complexity.)

4.How to test any algorithm? (There are two way to do test. a) Debugging  and Profiling. Debugging means checking of errors step by step. Profiling means Again analyse algorithm after removing error (time and space).

There are following criteria for algorithm:

1.Input

2. Output (at least one output generated), algorithm must design in such a way that will generate at least one output.

3. Definiteness (there is no any situation of indefinite and ambiguous), conditions in every algorithm must have well define loops and it must be terminated properly that means no infinite loop occur, no ambiguity  occur. It is sure algorithm must execute and complete the task.

4. Finite (program must terminate at finite number of steps, i.e finite loop),every algorithm must have well define loops and it must be terminated properly that means no infinite loop occur.

5. Effectiveness (it means less time, less space, correct result , task must be solved etc.), any algorithm is said to be effective if it will take less time to execute, take less space in memory for storage and generate correct result.

Algorithm :

An algorithm is a step by step procedure in order to solve a given problem. Generally English language is used to write any algorithm so that majority can understand. 

Program : It is a step by step procedure to solve a given problem and it is written by using any computer language such as  c ,c++, java, c# etc.

Way to design algorithm: There are basically two method are used to design any algorithm such as

1. Incremental Approach.

2. Divide and conquer approach.

Incremental Approach : 

It is a top down approach in which we proceed from start and compare elements in iterative manner and we finally get the solution.In this approach any algorithm is design is  by using stack. 

Example : bubble sort, insertion sort, selection sort etc.

Divide and Conquer Approach: 

In this approach large problem is divided into sub problem and each sub problem is solve recursively and combining these solution we get final solution of the problem. In this approach any algorithm is design is  by using array. 

Example: merge sort , quick sort , heap sort  etc.

ASYMPTOTIC  NOTATIONS:

It is used to analyse the bound (range) of functions whether it is lower bound, upper bound or in between bound. Here lower bound means minimum value, upper bound means maximum bound and in between bound means between Upper bound and minimum bound. 

The general idea of asymptotic notation is to analysis the efficiency of algorithms.

It is classified into following:

1. Lower bound notation. It is denoted by (omega)

2.Tight bound notation. It is denoted by (Theta)

3.Upper bound notation. It is denoted by (Big-oh)

Type of Notations: 

All notations are come under the above classification of notations. such as (Omega, Theta, Big-oh)

1. Big-oh Notation  (come under upper bound)

2. Big-omega Notation (come under lower bound)

3. Theta Notation (come under in-between bound (i.e between lower & upper))

4. Little-oh Notation 

5. Little-omega Notation

Note: Little-oh Notation  and Little-omega Notation are generally used for those algorithm which are large in size.

Big-oh Notation (O) :

It provide upper bound of function.

Example :

f(n) =O(g(n))

where: g(n) is upper bound of function f(n)

 it is when:  f(n) <= c g(n)  ; where c is positive constant.

for all n>=n₀  ; where n is input size.

If the condition f(n) <= c g(n) is true than we get n₀.

Let we explain with the help of example,

Q. Find the upper bound of the function  

    f(n) = 2n + 6

Sol: we know that f(n) <= c g(n)

where c is any positive constant and g(n) is upper bound.

Now we first find upper bound g(n) from the above equation f(n)=2n + 6

g(n) =highest power of n in equation, here it is 1

now   2n + 6 = c n    (since g(n)=n)  ------- equation 1

now we find upper bound in 2n + 6

for calculating upper bound simply add one n to 2n (term contain n) such as 

2n + n = 3n.

so we can write  2n + 6 = 3n   ------equation 2

Now compare equation 1 and 2

2n + 6 <= c n  and 

2n + 6 <= 3n

we get c=3

Now we put different value of n in equation  2n + 6 <= 3n  till the condition is not true such as:

n            2n + 6 <= 3n

1             8<=3               false

2            10<=6              false

3            12<=9              false

4            14<=12            false

5            16<=15            false

6            18<= 18           true

now stop checking

So we can write  f(n) = Og(n) for c=6 &  n>=6

Graphical representation:

Big-Omega Notation (Ω):

It provide lower bound of function

f(n) = Ω (g(n))

if f(n) >= c g(n) , where c is any positive constant

for all n >=n₀ , where n is any input constant.

Let we understand with the help of an example:

Example : Find the lower bound for the function  f(n) = 2n + 6

Sol:  

we know that f(n) >= c g(n)

where c is any positive constant and g(n) is upper bound.

Now we first find lower bound g(n) from the above equation f(n)=2n + 6

g(n) =highest power of n in equation, here it is 1

now   2n + 6 >= c n    (since g(n)=n)  ------- equation 1

now we find lower bound in 2n + 6

for calculating lower bound or tight bound is 2n only (term contain n).

So the equation will be: 2n + 6 >= 2n --------equation 2

Compare both equations 1 & 2 

2n + 6 >=c n

2n + 6 >= 2n

Note: since f(n)>=c g(n), where  cn is lower bound which is equivalent to 2n.

Now we put different value of n in equation  2n + 6 >= 2n  till the condition is not true such as:

n            2n + 6 >= 2n

1            7 >= 2        true

Graphical representation :

Theta Notation (θ) :

It is also known as sand witch notation.

It provide tight bound or in-between bound of a function 

f(n) = θ g(n)

Condition:  c1 g(n) <= f(n) <= c2 g(n) , where c1 7 c2 are positive constants.

Let we understand with the help of an example:

Example : Find the tight bound or in between for the function  f(n) = 2n + 6

Sol:  

we know that,  c1 g(n) >= f(n) <= c2 g(n)

here we know that 

lower bound =2n

upper bound  3n

Referenced by above questions

Now we put different value of n in equation  2n >=  f(n) <= 3n  till the condition is not true such as:

n            2n <=  (2n + 6) <= 3n 

1            2<=8<=3            false

2            4<=10<=6          false

3            6<=12<=9          false

4            8<=14<=12        false

5           10<=16<=15       false

6           12<=18<=18       true 

now stop checking

So we can write  f(n) = θ g(n) for all n>=6 , when c1=2 &  c2=3

Graphical representation:

 📌This is the end of this post.In this post I discussed about following topic such as introduction of Analysis Design Of Algorithm (ADA), We must know about , What is analysis ? What is design ? What is algorithm ? What is problems and how we solve it ?, We also discuss about design strategy and Asymptotic Notations such as Big-oh notation, Big-omega notation, Theta notation, Little-oh notation, Little-omega notation, Incremental and divide and conquer approach. I hope it is beneficial for you, we will meet in next post till continue reading....