Q. 1 a) Explain how to analyze an algorithm.**[07 M]**

**Ans :**

Analysis of Algorithm :

â€¢ Analysis of algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and space required for storage while implementation.

â€¢ It is used to measure the performance of the algorithms.

â€¢ It is also used for finding the computational complexity of algorithms.

â€¢ Performance analysis of an algorithm is done to understand how efficient that algorithm is compared to another algorithm that solves the same computational problem.

â€¢ Analysis of algorithm can be performed in following ways:

i) Worst-case

â€¢ It is the maximum number of steps taken on any instance of size A.

â€¢ In the worst-case analysis, the upper bound on the running time of an algorithm can be calculated.

â€¢ Worst-case analyses the case which causes a maximum number of operations to be executed.

ii)Best-case

â€¢ It is the minimum number of steps taken on any instance of size A.

â€¢ In the best case analysis, the lower bound on the running time of an algorithm can be calculated.

â€¢ Best-case analyses the case which causes a minimum number of operations to be executed.

iii) Average case

â€¢ It is an average number of steps taken on any instance of size A.

â€¢ In average case analysis, all possible inputs should be taken and then calculate computing time for all of the inputs.

â€¢ Then sum all the calculated values and divide the sum by the total number of inputs.

â€¢ In average case, the distribution of cases should be known.

â€¢ There are two ways to evaluate an algorithm which helps to analyze an algorithm performance:

1.Space requirement

2.Computation time

1. Space Complexity

â€¢ The space requirement is related to memory resource needed by the algorithm to solve a computational problem to completion.

â€¢ The program source code has many types of variables and their memory requirements are different.

â€¢ The space requirement can be divided into two parts.

a.Fixed Variables

â€¢ The fixed part of the program are the instructions, simple variables, constants that does not need much memory and they do not change during execution.

â€¢ They are free from the characteristics of an instance of the computational problem.

b.Dynamic Variables

â€¢ The variables depends on input size, pointers that refers to other variables dynamically.

â€¢ This type of memory requirement changes with instance of the problem and depends on the instance characteristics.

â€¢ It is given by the following equation.

S(P) = c+SP

Where, W(P) is space requirement

c is constant

SP is the instance characteristics

2.Time Complexity

â€¢ The time complexity is the amount of time required to run the program to completion.

â€¢ It is given by following.

T(P) = Compile time + run – time

P is the program

T(P) is the time complexity of program

Q. 1 b) Explain asymptotic notations in brief.[06 M]

**Ans :**

Different asymptotic notations used for analysis of algorithm :

The different asymptotic notations used for analysis of algorithm to represent the time complexity of algorithms are

1.Î¸ Notation

2.Big O Notation

3.Î© Notation

1) Î¸ Notation:

â€¢ The theta notation bounds a function from above and below, so it defines exact asymptotic behavior.

â€¢ For a given function g(n), we denote Î¸(g(n)) is following set of functions:

Î¸ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 <= c1g(n) <= f(n) <= c2g(n) for all n >= n0}

â€¢ The above definition means, if f(n) is theta of g(n), then the value f(n) is always between c1*g(n) and c2*g(n) for large values of n (n >= n0).

â€¢ The definition of theta also requires that f(n) must be non-negative for values of n greater than n0.

â€¢ Î¸ provides exact bounds.

Examples :

{ 100 , log (2000) , 10^4 } belongs to Î¸(1)

{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Î¸(n)

{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Î¸( n^2)

2)Big O Notation:

â€¢ The Big O notation defines an upper bound of an algorithm

â€¢ It bounds a function only from above.

â€¢ The Big O notation is useful when there is only an upper bound on the time complexity of an algorithm.

â€¢ For a given function g(n), we denote O(g(n)) is following set of functions:

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0}

â€¢ O provides exact or upper bounds.

Examples :

{ 100 , log (2000) , 10^4 } belongs to O(1)

U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to O(n)

U { (n^2+n) , (2n^2) , (n^2+log(n))} belongs to O( n^2)

Here, U represents union

3) Î© Notation:

â€¢ Î© notation provides an asymptotic lower bound.

â€¢ Î© Notation can be useful when there is lower bound on the time complexity of an algorithm.

â€¢ For a given function g(n), we denote by Î©(g(n)) the set of functions:

Î© (g(n)) = {f(n): there exist positive constants c and n0 such that 0 <= c*g(n) <= f(n) for all n >= n0}.

â€¢ Î© provides exact or lower bounds.

Examples :

{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Î©( n^2)

U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Î©(n)

U { 100 , log (2000) , 10^4 } belongs to Î©(1)

Here, U represents union

Login

Accessing this course requires a login. Please enter your credentials below!