Summer 2019 Q.1 Solution - Grad Plus

Summer 2019 Q.1 Solution

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 c1g(n) and c2g(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)

NIR W18 Q.1 Image1 Page 27 1 - Grad Plus
Fig a. θ Notation, f(n) = θ(g(n))

2)Big O Notation:
• The Big O notation defines an upper bound of an algorithm
• It bounds a function only from above.

NIR W18 Q.1a Image2 Page 28 2 - Grad Plus
fig b. O notation, f(n) = O(g(n))

• 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.

NIR W18 Q.1a Image3 Page 29 1 - Grad Plus
fig c. Omega notation, f(n) = Ω (g(n))

• 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


Scroll to Top

NAGPUR UNIVERSITY

PUNE UNIVERSITY

MUMBAI UNIVERSITY