Unit-I/Introduction

Unit – I
INTRODUCTION
Notion Of An Algorithm – Fundamentals Of Algorithmic Problem Solving – Important Problem
Types – Fundamentals Of The Analysis Of Algorithm Efficiency – Analysis Framework – Asymptotic
Notations And Its Properties – Mathematical Analysis For Recursive And Non-Recursive
Algorithms.

PART – A
NOTION OF AN ALGORITHM

1. What is an algorithm? Or Define an algorithm.[May 2006,2007, Nov 2008] (R)

Algorithm

An algorithm is defined as a collection of unambiguous instructions occurring in some

specific sequence and such an algorithm should produce output for given set of input in
finite number of time. Algorithm is basically a sequence of instructions written in simple
English language. The algorithm is broadly divided into two sections,
 Algorithm heading
 Algorithm body

2. What are the features of an algorithm? (U)

Features Of An Algorithm

More precisely, an algorithm is a method or process to solve a problem satisfying the

following properties:
 Finiteness-Terminates after a finite number .of steps
 Definiteness- Each step must be rigorously and unambiguously specified.
 Input-Valid inputs must be clearly specified.
 Output-Can be proved- to produce the correct output given a valid input.
 Effectiveness-Steps must be sufficiently simple and basic.

3. Define program proving and program verification. (R) [May 2014]

Program
A program is the expression of an algorithm in a programming language.

Algorithms + Data Structures = Programs

U20IT303/Design and Analysis of Algorithm Page | 1

 Unit-I/Introduction

Program Proving
Given a program and a formal specification, use formal proof techniques
(e.g. induction) to prove that the program behaviour fits the specification
Program Verification
Testing to determine whether a program works as specified.

4. Show the notion of an algorithm. (U) [Dec 2009 / May2013]

Notion Of An Algorithm

An algorithm is a sequence of unambiguous instructions for solving a problem in a finite

amount of time.

5. How to write an algorithm? (U)

Writing an algorithm

 Algorithm is a procedure consisting of heading and body.

 The heading section should write problem description, input and output.
 The body of an algorithm is written, in which various programming constructs like if, or,
while.
 The compound statements should be enclosed within {and} brackets.
 Single line comments are written using // as beginning of comment.

6. Difference between program and algorithm (A)

Program Vs Algorithm

Algorithm Program
1. Algorithm is finite. 1. Program need to be finite.

2. Algorithm is written using natural 2. Programs are written using a

language or algorithmic language. programming language

U20IT303/Design and Analysis of Algorithm Page | 2

 Unit-I/Introduction

7. Write an algorithm for sorting the elements. (C)

Algorithm sort (a, n)

for i  1 to n do
for j  i  1 to n  1 do
{
if ai  a j  then
{
temp  a[j]
a[i]  a[j]
a[j]  temp
}}
write (“List is sorted”)

8. Write an algorithm to find factorial of n number. (C)

Algorithm fact (n)

if(n  1) then
return 1
else
return n*fact(n-1)

9. Write an algorithm to count the sum of n numbers. (C)

Algorithm sum (1, n)

result  0
for i  1 to n do i  i+1
result  result + i
return result

10. Design an algorithm to compute the area and circumference of a circle. (C)
[Nov/Dec 2016]

Algorithm area & circumference(r)

area=3.14*r*r
circumference=2*3.14*r
return area
return circumference

U20IT303/Design and Analysis of Algorithm Page | 3

 Unit-I/Introduction

11.What are the ways to compute the gcd of two given numbers? (R)
Calculating Greatest Common Divisor
Problem Statement
The Greatest common Divisor (GCD) of two non-zero numbers a and b is basically the
largest integer that divides both a and b evenly i.e., with a remainder of zero.
GCD· - 3 methods
1. Euclid‟s algorithm
2. Consecutive integer checking algorithm
3. Finding GCD using repetitive f a c t o r s

12.Write the Consecutive Integer Checking algorithm to calculate the gcd of two
numbers. (AP)

Consecutive integer checking algorithm for computing gcd(m, n)

Step 1 :Assign the value of min{m, n} to t.

Step 2 :Divide m by t. If the remainder of this division is 0, go to Step 3;
otherwise, go to Step 4.
Step 3 :Divide n by t. If the remainder of this division is 0, return the value of
t as the answer and stop; otherwise, proceed to Step 4.
Step 4: Decrease the value of t by 1. Go to Step 2.

13. Give the Euclid’s algorithm for computing gcd(m,n). (U) [May/June 2016]

Euclid’s algorithm

Euclid's algorithm is based on applying related equality gcd (m, n) gcd (n, m mod n)

ALGORITHM Euclid(m, n)
//Computes gcd(m, n) by Euclid’s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n = 0 do
r ←m mod n
m ←n
n ←r
return m

U20IT303/Design and Analysis of Algorithm Page | 4

 Unit-I/Introduction

FUNDAMENTALS OF ALGORITHMIC PROBLEM SOLVING

14.What are six step processes in algorithmic problem solving?[Dec 2009] (U)
Algorithmic Problem Solving

1. Understanding the problem

2. Decision Making .
 Ascertaining the capabilities of a computational device
 Choosing between exact and approximate problem solving
 Appropriate data structures
 Algorithm Design Techniques
3. Specification of algorithm
4. Algorithmic verification
5. Analysis of algorithm
6. Implementation or coding of algorithm

15.Draw the flow diagram of algorithm design and analysis process. (R)

U20IT303/Design and Analysis of Algorithm Page | 5

 Unit-I/Introduction

16.What is instance? (R)

Instance of an Algorithm
An input to an algorithm specifies an instance of the problem the algorithm solves. It is
very important to specify exactly the set of instances the algorithm needs to handle.

17.Compare sequential algorithm and parallel algorithm? (A)

Sequential Algorithm Parallel Algorithm

In Random Access Machine (RAM), A parallel algorithm is one, which can be

instructions are executed one after another, executed a piece at a time on many different
one operation at a time. Accordingly, processing devices and then put back together
algorithms designed to be executed on such again at the end to get the correct result.
machines are called sequential algorithms.

18.Write about exact algorithm and approximation algorithm. (U)

Exact Algorithm Vs Approximation Algorithm

The important decision is to decide whether the problem is to be solved exactly or

approximately
Exact Algorithm - If the problem needs to be solved correctly then we need exact algorithm.
Approximation Algorithm- If the problem is so complex that we won‟t get the exact solution
then in that situation we need to choose approximation algorithm. The typical example of
approximation algorithm is travelling salesman problem.

19.What are the methods used for specifying an algorithm? (R)

Specifying An Algorithm

(i) Natural Language- free style and step by step format

(ii) Pseudocode- mixture of a natural language and programming language like constructs.
Pseudocode is usually more precise than natural language, and its usage
often yields more succinct algorithm descriptions.
(iii)Flowchart - method of expressing an algorithm by a collection of connected geometric
shapes containing descriptions of the algorithm's steps.

U20IT303/Design and Analysis of Algorithm Page | 6

 Unit-I/Introduction

20.What is algorithm design technique? What are different algorithm design

techniques/strategies? (R)

Algorithm Design Technique

An algorithm design technique (or "strategy" or "paradigm") is a general approach to

solving problems algorithmically that is applicable to a variety of problems from
different areas of computing.
1. Brute force 5. Greedy approach
2. Divide and conquer 6. Dynamic programming
3. Decrease and conquer 7. Backtracking
4. Transform and conquer 8. Branch and bound

21.How to implement an algorithm? (U)

Implementation Of An Algorithm

 The implementation of an algorithm is done by suitable programming language.

 For example, object oriented programming language like C++ or JAVA.
 While writing a program for given algorithm it is essential to write an optimized code.
This will reduce the burden on compiler.

22.List the characteristics of an algorithm. (U)

Characteristics Of An Algorithm

 Input
 Output
 Definiteness
 Finiteness
 Efficiency
 Un ambiguity

23.Define algorithm verification. (R)

Algorithm Verification

 Algorithmic verification means checking correctness of an algorithm – checking

whether the algorithm gives correct output in finite amount of time for a valid set of
input.
 A common method of proving the correctness of an algorithm is by using mathematical
induction.

U20IT303/Design and Analysis of Algorithm Page | 7

 Unit-I/Introduction

24.What are the factors to be considered while analyzing an algorithm? (A)

Factors for Algorithm Analysis

 Time efficiency of an algorithm

 Space efficiency of an algorithm
 Simplicity of an algorithm
 Generality of an algorithm
 Range of input

25.Define Algorithm validation. [Dec 2012] (U)

The process of measuring the effectiveness o f an algorithm before it is coded to know
whether the algorithm is correct for every possible input. This process is called validation.

26.Write about simplicity of an algorithm. (U)

Simplicity Of An Algorithm

 Simplicity of an algorithm means generating sequence of instructions which are easy to

understand.
 While simplifying an algorithm we have to compute any predefined computations or
some complex mathematical derivation.
 Finding out bugs from algorithms or debugging the program becomes easy when an
algorithm is simple.

27.What is generality? (U)

Generality

 Generality shows that sometimes it becomes easier to design an algorithm in more

general way rather than designing it for particular set of input.
 For example, designing an algorithm for finding GCD of any two numbers is more
appealing than that of particular two values. But sometimes it is not all required to design
a generalized algorithm.

28.Write an algorithm to find the number of binary digits in the binary representation of
a positive decimal integer. [May 2015] (C)

Algorithm BinRec(n)
//Input: A positive decimal integer n
//Output: The number of binary digits in n's binary representation
if n=l
return 1
else
return BinRec([n/2])+ 1

U20IT303/Design and Analysis of Algorithm Page | 8

 Unit-I/Introduction

IMPORTANT PROBLEM TYPES

29.Explain the various types of problems that can be solved using algorithm. (R)
Types Of Problems

1. Sorting
2. Searching
3. String Processing
4. Graph problems
5. Combinatorial Problems
6. Geometric problems
7. Numerical problems.

30.What is sorting?(R)
Sorting

Problem Statement : Sorting means arranging the elements in increasing order or in

decreasing order.
Problem Description:
Sorting .is the operation of arranging the records of a table according to the key value of the
each record.
Example : Sort student records in alphabetical order of names or by student number or by
student grade-point average(Key)

31.What are the properties used for analysing various sorting algorithms? (U)
Properties of Sorting Algorithms

Stable
 A sorting algorithm is called stable, if it preserves the relative order of any two equal
elements in its input.
 In other words, if an input list contain two equal elements in positions i and j, where
i<j, then in the sorted list they have to be in position i' and j' respectively, such
that i' <j'
In-place
An algorithm is said to be in-place if it does not require extra memory, except, possibly
for a few memory units.

U20IT303/Design and Analysis of Algorithm Page | 9

 Unit-I/Introduction

32.Write about geometric problem.(U)

Geometric Problem

 Geometric algorithms deal with geometric objects such as points,lines and polygons.
 The procedure for solving a variety of .geometric problems includes the problems
of constructing simple geometric shapes such as triangles, circles.
 The two classic problems of computational geometry ate:
 Closest pair problem
Given n points in the plane, find the closest pair among them.
 Convex hull problem
Find the smallest-convex polygon that would include all the points of a
given set.

33.What do you mean by Combinatorial Problem? (U)

Combinatorial Problem

Problem Statement: A combinatorial object such as a permutation a combination or a subset

that satisfies certain constraints and has some desired property such as maximizes a value or
minimizes a cost .
Examples: Travelling Salesman Problem
Graph Colouring Problems

FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM

EFFICIENCY-ANALYSIS FRAMEWORK

34.What do you mean by linear search? [Nov 2011, May 2012] (R)
Sequential Search or Linear Search

Problem Statement
To search for a given item using some search key K in a list of „n' elements by checking
successive elements of the list until a match with the search key is found or the list is
exhausted.

35.What are the factors used to measure the performance of an algorithm? (A)
Factors used to measure the performance of an algorithm

The performance of an algorithm can be measured by computing two factors:

1. Amount of time required by an algorithm to execute - Time Complexity
2. Amount of storage required by an algorithm - Space Complexity

Design and Analysis of Algorithm Page | 10

 Unit-I/Introduction

36.What is Space Complexity? [May 2010] [Dec 2012] (R)

Space Complexity

Space efficiency, also called Space complexity, refers to the amount of memory units
required by the algorithm to run in addition to the space needed for its input and output.
Factors for computing the space complexity - Constant and Instance characteristics.
Space requirement S(P) can be given as

S(p) = C+
Where C is a constant i.e. fixed part and it denotes the space of inputs and outputs

37.What is time complexity? [May 2010] [Dec 2012](R)

Time Complexity

 The time complexity of an algorithm is the amount of computer time required by an

algorithm to run to completion.
 The time complexity is given in terms of frequency count.
 Frequency count is a count denoting number of times of execution of a statement.
Normally time complexity is denoted in terms of Oh notation (  ).

38.Differentiate time complexity from space complexity. April/May 2010. (A)

Time Complexity Vs Space Complexity
Time Complexity Space Complexity

 Time complexity of an algorithm  Space complexity of an algorithm

means the amount of time taken by means the amount of space (memory)
an algorithm to run. taken by an algorithm.
 By computing time complexity we  By computing space complexity we
come to know whether the algorithm can analyze whether an algorithm
is slow or fast. requires more or less space.

39.Define frequency count with an example. (U)

Frequency Count
Frequency count is a count denoting number of times of execution of statement.
For example calculating sum of n numbers in an array.

for (i=0; i<n; i++)

{
sum=sum+a[i];
}
Design and Analysis of Algorithm Page | 11
Unit-I/Introduction

Statement Frequency Count

i=0 1

i<n (n+1)-condition true, n times- condition

false.

i++ n times

Sum=sum+a[i] n times

Total 3n+2

Thus we get frequency count to be 3n+2.

40.How will you measure input size of algorithms? (A)

1. Measuring an Input's size

All algorithms run longer on larger inputs.

Examples
Evaluating a Polynomial
In problem of evaluating a polynomial p(x) = an X n + ....+ ao of degree n
Time Taken by the algorithm α degree or the number of its coefficients [Input Size]

41.What is meant by order of growth? (U)

Order Of Growth

Measuring the performance of an algorithm in relation with the input size n is called order of
growth. For example, the order of growth for varying input size of n is as given below.

N log n n log n n2 2n

1 0 0 1 2

2 1 2 4 4

4 2 8 16 16

Page | 12
 Unit-I/Introduction

42.List the properties of order of growth. (U)

Properties of Order of Growth

 If F1 (n) is order of g1 (n) and F2 (n) is order of g2 (n), then

F1 (n) +F2 (n) .

 Polynomials of degree m  n m  .That means maximum degree is considered from the
polynomial.
 1  log n  n  n 2   2 n  .

2
43.Compare the orders of growth of n(n-1)/2 and n . [May/June 2016]
2
Orders of growth of n(n-1)/2 and n

2
n(n-1)/2 = n! n
1!=1 12 = 1
2!=2x1=2 22 =2
3!=3x2x1=6 32=9
4!=4x3x2x1=24 42=16

2
Therefore N(n-1)/2 has higher order of growth than n

44.List the classification of different efficiency classes. (R)

Efficiency Classes

 Constant
 Logarithmic
 Linear
 Quadratic
 Cubic
 Exponential
 Factorial

U20IT303/Design and Analysis of Algorithm Page | 13

 Unit-I/Introduction

45.What is meant by time space tradeoff? (U)

Time Space Tradeoff

 Time space tradeoff is basically a situation where either space efficiency (memory
utilization) can be achieved at the cost of time or time efficiency (performance
efficiency) can be achieved at the cost of memory.
 Consider the programs like compilers in which symbol table is used to handle the
variables and constants. Now if entire symbol table is stored in the program then the time
required for searching or storing the variable in the symbol table will be reduced but
memory requirement will be more.

46. How to measure the running time?(A)

Basic Operation

The main objective is to identify the most important operation of the algorithm, called
the
Basic Operation - the operation contributing the most to the total running time

Running time α Number of times the basic operation is executed

Computing execution time using basic operation

The formula to compute the execution time using basic operation is

T(n) ~ C(n)

Where
T(n) - running time
C(n) - no. of times this operation is executed.
Cop - execution time of algorithms basic operation.

47.What are the drawbacks to measure the runtime of an algorithm? (U)

Drawbacks to measure the runtime of an algorithm

The runtime of an algorithm cannot be measured in standard unit of time because in multiuser
system running time depends on many factors such as:-
 System load
 Number of other program running
 Instruction set used
 Speed of underlying hardware
U20IT303/Design and Analysis of Algorithm Page | 14
 Unit-I/Introduction

48.Define worst case time complexity. (R)

Worst Case Time Complexity

Worst case time complexity is a time complexity when algorithm runs for a longest time. We
can denote the worst case complexity as,
Cworst = n

The algorithm guarantees that for any instance of input which is of size n, the running time will
not exceed Cworst (n). Hence the worst case time complexity gives important information about
the efficiency of algorithm.

49.What is average case analysis? May/June 2014. (U)

Average Case Analysis

Average complexity gives information about the behavior of an algorithm on specific random
input.
Example, for sequential search and P be a probability of getting successful search. n is the total
number of elements in the list.
Cavg (n) = Probability of successful search + Probability of unsuccessful search

50.What is meant by best case time complexity? (U)

Best Case Time Complexity

Best case time complexity is a time complexity when an algorithm runs for short time. In the
searching algorithm the element key is searched from the list of n elements. We can denote the
best case time complexity as
Cbest = 1
The algorithm guarantees that for any instance of input which is of size n, the running time will
not exceed Cbest (n).

51. Analyse the time efficiency of linear search? Nov/Dec 2011. (A)
Analysis of Linear Search

For analysis of linear search will consider 3 cases.

In linear search algorithm,
Best case : if we get the element at the first place then it is a best case time complexity because
in this case algorithm takes minimum amount of time to run to its completion.

U20IT303/Design and Analysis of Algorithm Page | 15

 Unit-I/Introduction

Worst case : if we get the element at the first place then it is a best case time complexity
because in this case algorithm takes minimum amount of time to run to its completion.

Average case : if the element is present at the end of the list or it is not all present in the list,
then it is called worst case time complexity because in this case algorithm takes maximum
amount of time to run to its completion

52.What do you mean by Amortized Analysis? (U)

Amortized Analysis

 Amortized analysis finds the average running time per operation over a worst
case sequence of operations
 It applies not to a single run of an algorithm but rather to a sequence of operations
performed on the same data structure.
 It turns out that in some situations a single operation can be expensive, but the total time
for an entire sequence of n such operations is always significantly better than the worst-
case efficiency of that single operation multiplied by n.
 So we can “amortize” the high cost of such a worst-case occurrence over the entire
sequence in a manner similar to the way a business would

53.Using the step count method analyze the time complexity when 2m*n matrices
are added. [May 2011] (E)

Time complexity of Matrix addition

Consider the following code:

for (i =0; i <m; i++)
{
for (j= 0 ; j < n ; j++)
{
C[i][j]=a[i][j] +b[i][j]
}
}
Statement Step count
i=0 1
i<m m+1
i++ m
j=0 m
j<n (n+1)m
j++ (n+1)m
C[i][j] = a[i][j] + b[i][j] nm
Total 3nm+5m+2
Time Complexity ~ O(mn)
U20IT303/Design and Analysis of Algorithm Page | 16
 Unit-I/Introduction

ASYMPTOTIC NOTATIONS AND ITS PROPERTIES

54.Define asymptotic notation. [May 2014] [Nov 2011] (R)

Asymptotic Notations

 Asymptotic notation is a shorthand way to represent the time complexity.

 Using asymptotic notations we can give time complexity as “fastest possible”, “slowest
possible” or “average time”.
 Various notations such as ,  and  used are called as asymptotic notations.

55.Define Big oh (O). [May 2012, May 2013] (R)

Big Oh Notation

The big Oh notation is denoted by „  ‟. It is a method of representing the upper bound of

algorithms running time. Let F(n) and g(n) be two non-negative functions. Let n0 and constant c
are two integers such that n0 denotes some values of input and n > n0. Similarly c is some
constant such that c > 0.

F n  c  g n

Then F(n) is big oh of g(n). It also denoted as F n  g n .

56.What is the properties of big-Oh notation. [Nov 2011] (U)

Properties of big-oh notation

 If there are two functions f1 n  and f 2 n  such that f1 n  g1 n and f 2 n  g 2 n
then f1 n  + f 2 n  =max g1 n, g 2 n.
 If there are two functions f1 n  and f 2 n  such that f1 n  g1 n and f 2 n  g 2 n
then f1 n  * f 2 n  = g1 n * g 2 n .
 If there exists a function f1 such that f1  f 2 * c where c is a constant then, f1 and f 2 are
equivalent. That means
 If f n  g n and  f1  f 2    f1    f 2 . g n  hn then f n  hn.

57.Define the asymptotic notation "Omega" (Ω). [May2013j (R)

"Omega" (Ω).

A function F(n) is said to be in  (g(n)) if F(n) is bounded below by some positive constant
multiple of g(n) such that

F n  c  g n for all n  n0 .

It is denoted as F n  g n .

Design and Analysis of Algorithm Page | 17

 Unit-I/Introduction

58.Define the asymptotic notation "theta" (Ө). (R)

"Theta" (Ө).

The theta notation is denoted by „  ‟. By this method the running time is between upper bound
and lower bound. Let F(n) and g(n) be two non-negative functions. There are two positive
constants namely c1 and c2 such that,

c1 g (n)  F n  c2 g n .

Then we can say that F n  g n .

59.Write down the properties of asymptotic notations. [May 2015] (U)

Properties of Asymptotic Notations

 If F1 (n) is order of g1 (n) and F2 (n) is order of g2 (n), then

F1 (n) +F2 (n)  max g1 n, g 2 n .

 Polynomials of degree m  n m  .That means maximum degree is considered from the
polynomial.
 1  log n  n  n 2   2 n  .
 Exponential functions an have different orders of growth for different values of a.

MATHEMATICAL ANALYSIS FOR RECURSIVE AND NON-

RECURSIVE ALGORITHMS.

60.What is a recurrence equation? [April/May 2010]. (R)

Or
Define Recurrence Relation. [Nov/Dec 2016]

Recurrence Equation

The recurrence equation is an equation that defines a sequence recursively. It is normally in

following form,
T n  T n  1  n for n  0 …………………….. (1)
T 0  0 …………………….. (2)

Here equation 1 is called recurrence relation and equation 2 is called initial condition. The
recurrence equation can have infinite number of sequences. The general solution to the
recursive function specifies some formula.

Design and Analysis of Algorithm Page | 18

 Unit-I/Introduction

61.List the methods for solving recurrence equations. (R)

Methods for Solving Recurrence Equations

 Substitution method
 Forward substitution (This Process continued until some formula is guessed)
 Backward substitution (Values are substituted recursively)
 Master method
 Tree method (recursive function)

62.What is substitution method mention its types. April/May 2010. (R)

Substitution Method

The substitution method guess for the solution is made. There are two types of substitution:
 Forward substitution
 Backward substitution
Forward substitution method: This method makes use of an initial condition in the initial term
and value for the next term is generated. This process is continued until some formula is
guessed.
Backward substitution method : Values are substituted recursively in order to derive some
formula.

63.Solve the following recurrence equation M n  M n  1  2, M 1  0 using backward

substitution method. (AP)

Solution

M (n) = M (n − 1) + 2

= [M (n − 2) + 2] + 2 = M (n − 2) + 2 + 2

= [M (n − 3) + 2] +2+2 = M (n − 3) +2+2 + 2

= ...

= M (n − i) + 2i

Where i=n-1 then

= M (1) + 2(n − 1) = 2(n − 1)

.
M (n) = 2(n − 1)

Design and Analysis of Algorithm Page | 19

 Unit-I/Introduction

64.Solve the following recurrence equation S n  S n  1  4n for n  0 and S 0  1 using
backward substitution method. (AP)

Solution
S (n) = S (n − 1) + 4n

= [S (n − 2) + 4(n − 1)] + 4n = S (n − 2) + 4(n − 1) + 4n

= [S (n − 3) + 4(n − 2)] + 4(n − 1) + 4n = S (n − 3) + 4(n − 2) + 4(n − 1) + 4n

= ...

= S (n − i) + 4(n − i + 1) + 4(n − i +2) +... + 4n

= ...

= S (0) + 4 · 1 +4 · 2 + ... + 4n = 1+4(1 + 2 +... + n) = 1 + 4n (n + 1)/2 = 2n2 + 2n+1

S (n) = 2n2 + 2n+1

65.Solve the following recurrence equation Cn  Cn / 2  Cn / 2  1, for n  1, C1  0
(solve for n=2k). (AP)

Solution

Solving it for n = 2k by backward substitutions yields the following:

C (2k) = 2C (2k-1) + 1

= 2[2C (2k-2) +1] +1 = 22C (2k-2) + 2 + 1

= 22[2C (2k-3) + 1] + 2 + 1 = 23C (2k-3) + 22 + 2 + 1

= ...

= 2iC (2k-i) + 2i-1 +2i−2 + ... + 1

= ...

= 2kC (2k−k) + 2k−1 +2k−2 + ...+1 = 2k −1 = n − 1.

=n−1

Design and Analysis of Algorithm Page | 20

 Unit-I/Introduction

66.Solve the following recurrence equation An  2 An  1  1 and A0  0 using backward
substitution method. (AP)

Solution
A (n) = 2A (n − 1) + 1

= 2[2A (n − 2) + 1] + 1 = 22 A (n − 2) + 2+ 1

= 22[2A (n − 3) + 1] + 2 + 1 = 23 A (n − 3) + 22 + 2+ 1

= ...

= 2iA (n − i) + 2i−1 +2i−2 + ... + 1

= ...

= 2nA (0) + 2n−1 + 2n−2 + ... + 1 = 2n−1 + 2n−2 + ... + 1 = 2n − 1.

A (n) =2n − 1.

67.Solve the following recurrence equation Qn  Qn  1  2n  1 for n > 1, Q1  1. (AP)

Solution

Computing the first few terms of the sequence yields the following:

Q(2) = Q(1) + 2 · 2 − 1 = 1 + 2 · 2 −1 = 4;

Q(3) = Q(2) + 2 · 3 − 1 = 4 + 2 · 3 −1 = 9;

Q(4) = Q(3) + 2 · 4 − 1 = 9 + 2 · 4 −1 = 16.

Thus, it appears that Q(n) = n2. We‟ll check this hypothesis by substituting this formula into the
recurrence equation and the initial condition. The left hand side yields Q(n) = n2. The right hand
side yields

Q(n − 1) + 2n −1 = (n − 1)2 +2n −1 = n2.

68.Define tree method. (R)

Tree Method

 The recurrence relation can also be solved using tree method.

 In this method, a recursion tree is built in which each node represents the cost of a single
sub problem in the form of recursive function invocations.
 Then we sum up the cost at each level to determine the overall cost.
 Thus recursion tree helps us to make a good guess of the time complexity.
Design and Analysis of Algorithm Page | 21
 Unit-I/Introduction

69.What is the general plan for analyzing efficiency of non recursive algorithm? (U)
General plan for analyzing efficiency of non recursive algorithm

i. Decide the input size based on parameter n.

ii. Identify algorithms basic operation.
iii. Check how many times the basic operation is executed.
iv. Set up a sum for the number of times the basic operation is executed.
v. Simplify the sum using standard formula and rules.

70.What is the general plan for analyzing efficiency of recursive algorithm? (U)
General plan for analyzing efficiency of recursive algorithm

i. Decide the input size based on parameter n.

ii. Identify algorithms basic operation.
iii. Check how many times the basic operation is executed.
iv. Set up the recurrence relation with some initial condition and expressing the
basic operation.
v. Solve the recurrence or atleast determine the order of growth.

71.Define master theorem. (R)

Master Theorem

We can solve recurrence relation using a formula denoted by master‟s method.

T n  aT a / b  F n Where n  d and d is some constant.

Then the master theorem can be stated for efficiency analysis as:-
If F n  is n d  where d  0 in the recurrence relation then,

1. T n   n d   if a  b d

2. T n  n log n

d
if a  b

3. T n  n 
logb a
if a  b d

72.Solve the following recurrence relation T n   4T    n using master theorem. (AP)

n
2

Solution:

We will map this equation with

T n  aT n / b  f n Now f n  is n, a=4 and b=2 and a  b d . 4  21

T n   n logb a 
 n log2 4 
= n 2   log 2 4  2

Hence time complexity is n 2  .

Design and Analysis of Algorithm Page | 22
 Unit-I/Introduction

73.Solve the following recurrence relation Cn  Cn  1  1, C0  1 using substitution
method. (AP)

Solution:

C (n) = C (n − 1) + 1

= [C (n − 2) + 1] + 1

= C (n − 2) + 2

= ...

= C (n − i) + i

= ...

= C (0) + n

C (n) = 1+n

Design and Analysis of Algorithm Page | 23

 Unit-I/Introduction

PART – B
NOTION OF AN ALGORITHM

1. Explain the notion of an algorithm with diagram. [16M] [May 2014] (U)

Notion Of An Algorithm
Algorithm

An algorithm is defined as a collection of unambiguous instructions occurring in some specific

sequence and such an algorithm should produce output for given set of input in finite number of
time. Algorithm is basically a sequence of instructions written in simple English language.

Characteristics of an algorithm I Features of an Algorithm

1. Input  Zero or more quantities are externally supplied.

2. OutputAt least one quantity is produced.
3. Definiteness  Each instruction is clear and unambiguous.
4. Finiteness  For all cases the algorithm terminates after a finite number of steps.
5. EfficiencyEvery instruction must be very basic. It should be efficient.
6. Non - ambiguity  An algorithm must be expressed in a fashion that is completely
free of ambiguity.
7. Correctness  Algorithms should be concise and compact to facilitate verification
of their correctness.

Structure of an Algorithm
Algorithm heading
 Name Of Algorithm
 Problem Description
 Input & Output
Algorithm Body
 Logical Body of the Algorithm
 Programming Constructs

Design and Analysis of Algorithm Page | 24

 Unit-I/Introduction

Rules for writing an algorithm

1. Heading
Algorithm is a product consisting of heading and body. The heading consists of
keyword algorithm and name of the algorithm and parameter list. The syntax is
Algorithm name (p1, p2, pn)
Then in the heading section we should write following things:
 Problem Description
 Input
 Output
2. Body Of An Algorithm
Then body of an algorithm is written, in which various programming constructs like if,
for, while or some assignment statement may be written.
3. The compound statements should be enclosed within {and} brackets.
4. Single line comments are written using // as beginning of comment.
5. The identifier should begin by latter and not by digit. An identifier can be a
combination of alphanumeric string.
6. Data Types
 It is not necessary to write data types explicitly for identifiers. It will be
represented by the context itself.
 Basic data types  integer, float, and char, Boolean
 Compound data type structure or record
 The pointer type is also used to point memory locations.
7. Operators
 Boolean operators  true or false
 Logical operators  AND, OR, NOT
 Relational operators  <, <=, >, >=, =, !=.
 Assignment Operator (=)
8. Array Indices
 Stored with in square brackets []. The index of array usually starts at zero.
 The multidimensional arrays can also be used in algorithm.
9. Inputting And Outputting  read and write.
For example:
write ("this message will be displayed on console ");
read (Val);
10. Conditional Statements  if -then - else

if (condition)
then statement
else
statement

Design and Analysis of Algorithm Page | 25

 Unit-I/Introduction

11. While statement

while (condition) do
{
Statement 1
Statement 2
.....
Statement n
}

12. for loop

for (variable initialization;Condition;Increment/Decrement)
{
Statement 1
Statement 2
.....
Statement n
}

13. repeat - until statement

repeat
Statement 1
Statement 2
.....
Statement n
until (condition)

14. break statement  used to exit from inner loop.

15. return statement used to return control from one point to another.

Note:The statements in an algorithm executes in sequential order i.e. in the same order as
they appear - one after the other

Implementation of algorithms

 An algorithm describes what the program is going to perform. It states some of the
actions to be executed and the order in which these actions are to be executed.
 The various steps in developing algorithm are,
1. Finding a method for solving a problem.
2. The next step is to validate the algorithm.
3. Finally, implement the algorithm in terms of programming language.

Design and Analysis of Algorithm Page | 26

 Unit-I/Introduction

Order of an algorithm

The order of an algorithm is a standard notation of an algorithm that has been developed to
represent function that bound the computing time for algorithms. It is an order notation. It is
usually referred as O-notation.
Example
Problem size = 'n'
Algorithm = 'a' for problem size n
The document mechanism execution = Cn2 times
where C - constant

Order Of The Algorithm 'a' = O(n2)

where n2 = Complexity of the algorithm 'a'.

Program

 A set of explicit and unambiguous instructions expressed using a programming

languages constructs is called a program.

 A program is the expression of an algorithm in a programming language.

Algorithms + Data Structues  Progams

 An algorithm can be converted into a program, using any programming language.

Example: Pascal,Fortran, COBOL, C and C ++

2. Write an algorithm to count the sum of n numbers. [6M] (C)

Algorithm sum (1, n)

//Problem description: A lgorithm for finding the sum of given n numbers
//Input: 1 to n numbers
//Output: the sum of n numbers
result = 0
for i 1 to n
do i -E- i+l
Result +- result + i
Return result

Design and Analysis of Algorithm Page | 27

 Unit-I/Introduction

3. Write an algorithm to check whether given number is even or odd. [6M] (C)

Algorithm eventest (val)

//Problem description: this algorithm test whether given
//number is even or odd
//Input: the number to be tested i.e .val
//IOutput: appropriate messages indicating even or odd
if (val % 2 = 0) then
write ("given number is even ")
else
write ("given number is odd")

4. Write an algorithm for sorting the elements. [6M] (C)

Algorithm sort (a, n)

//Problem description: sorting the elements in ascending order
//Input: an array in which the elements in ascending orders&n total number of elements in
//the array
//Output: the sorted array
for i 1 to n do
for j i + 1 to n-l do
if (a[i]>a[j] then
{
temp +- a[i] a[i] +-a[j] a[j] +-temp
}
write (" list is sorted ")

5. Write an algorithm to find factorial of n number. [6M] (C)

Algorithm fact (n)

//Problem description: this algorithm finds the factorial for given number n
//Input : the number n of which the factorial is to be calculated.
//Output: factorial value of given n number.
if( n ≥ 1) then
return 1
else return n*fact(n-1)

Design and Analysis of Algorithm Page | 28

 Unit-I/Introduction

6. Write an 'algorithm to perform multiplication of two matrices.,[6M] (C)

Algorithm mul (A, b, n)

//Problem description: this algorithm is for computing multiplication of two matrices
//Input: the two matrices A, B and order of them as n
//Output: The multiplication result will be in matrix c
for i «- 1 to n do
for j «- 1to n do
c [i,j] «- 0
for k <e- 1 to ndo
c[i ,j ] «-c[i, j] +a[i;k]b[k,j]

7. Explain how various algorithms can be implemented for calculating greatest

Common Divisor. [16M] (AP)

Calculating Greatest Common Divisor

Problem Statement
The Greatest common Divisor (GCD) of two non-zero numbers a and b is basically the
largest integer that divides both a and b evenly i.e., with a remainder of zero.
GCD· - 3 methods
1. Euclid‟s algorithm
2. Consecutive integer checking algorithm
3. Finding GCD using repetitive f a c t o r s

Method-I
Euclid's algorithm to compute Greatest. Common Divisor (GCD) of two non-
negative integers.

Euclid's algorithm is based on applying related equality

gcd (m, n) gcd (n, m mod n)

Until m=0,n=0
Where m mod n is the remainder of the division of m by n

Euclid’ Method for calculating gcd (m,n)

Step 1: Start
Step 2: If n = 0, return the value of m as the answer and stop, otherwise proceed to step 3.
Step 3: Divide m by n and assign the value of the remainder to r.
Step.4: Assign the value of n to m and the value of r t o n. Goto step 2

Design and Analysis of Algorithm Page | 29

 Unit-I/Introduction

ALGORITHM Euclid(m, n)
//Computes gcd(m, n) by Euclid’s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n = 0 do
r ←m mod n
m ←n
n ←r
return m

Example: gcd (60,24) can be computed as follows:

gcd (60,24)
gcd (m, n); m =60, n=24;
m/n = 2 (remainder 12)
n=m=24; r=n=12
gcd (24, 12)
m/n = 2 (remainder 0)
n=m=12; r=n=0
gcd (12, 0) =12
Hence,

gcd(60, 24) = gcd(24,12)=gcd(12,0)=12

Method II
Consecutive Integer Checking Algorithm

 In this method while finding the GCD of a and b we first of all find the minimum value
of them.
 Suppose if value of b is minimum then we start checking the divisibility by each
integer which is lesser than or equal to b.
Example:
a = 15 and b =10 then t= min( 15,10)
since 10 is minimum we will set value of t = 10 initially.

Consecutive integer checking algorithm for computing gcd(m, n)

Step 1 :Assign the value of min{m, n} to t.
Step 2 :Divide m by t. If the remainder of this division is 0, go to Step 3;
otherwise, go to Step 4.
Step 3 :Divide n by t. If the remainder of this division is 0, return the value of
t as the answer and stop; otherwise, proceed to Step 4.
Step 4: Decrease the value of t by 1. Go to Step 2.

Design and Analysis of Algorithm Page | 30

 Unit-I/Introduction

Method III
Finding GCD using repetitive factors

The third procedure for finding the greatest common divisor is middle school procedure

Middle-school procedure for computing gcd(m, n)

Step 1: Find the prime factors of m.
Step 2 :Find the prime factors of n.
Step 3 :Identify all the common factors in the two prime expansions found in Step 1 and Step 2
times(If p is a common factor occurring pm and pn times in m and n, respectively, it
should be repeated min{pm,pn} times.)
Step 4 :Compute the product of all the common factors and return it as the
greatest common divisor of the numbers given.

Example: gcd (60,24) can be computed as follows:

FUNDAMENTALS OF ALGORITHMIC PROBLEM SOLVING

8. Explain the Fundamentals of Algorithmic problem solving. [May 2014-

16M] (R)

Fundamentals of Algorithmic problem solving

Sequential steps in designing and analysing an algorithm :

1. Understanding the problem
2. Ascertaining the capabilities of a computational device
3. Choosing between exact and approximate problem solving
4. Deciding on appropriate data structures
5. Algorithm Design Techniques
6. Methods of specifying an algorithm
7. Proving an algorithm's correctness
8. Analysing an algorithm
9. Coding an algorithm

1. Understanding the problem

To design an algorithm, understand the problem completely by reading the problem's

description carefully.
 Read the problem description carefully and clear the doubts.
 Specify exactly the range of inputs the algorithm need to handle
 Once the problem is clearly understandable, determine the overall goals but it should be
in a precise manner.
 Then divide the problem into smaller problems until they become manageable size-
Instance of the problem
Design and Analysis of Algorithm Page | 31
 Unit-I/Introduction

2. Ascertaining the capabilities of a computational device

Sequential Algorithm Parallel Algorithm

Instructions are executed one after another, Instructions are executed in parallel or
one operation at a time. This is concurrently
implemented in RAM model.

3. Choosing between exact and appropriate problem solving

The next principal decision is to choose between solving the problem exactly and solving the
problem approximately.

Exact Algorithm Vs Approximation Algorithm

The important decision is to decide whether the problem is to be solved exactly or

approximately
Exact Algorithm - If the problem needs to be solved correctly then we need exact algorithm.
Approximation Algorithm- If the problem is so complex that we won‟t get the exact solution
then in that situation we need to choose approximation algorithm. The typical example of
approximation algorithm is.
There are important problems that simply cannot be solved exactly such as
 Extracting square roots.
 Solving non-linear equations.
 Evaluating definite integrals.
 Travelling Salesman Problem
4. Deciding on appropriate data structures

Data structure is important for both design and analysis of algorithms.

Algorithm + Data Structures Programs

In Object Oriented Programming, the data structure is important for both design and
analysis of algorithms.
The variability in algorithm is due to the data structure in which the data of the program are
stored such as
1. How the data are arranged in relation to each other?
2. Which data are kept in memory?
3. Which data are kept in files and how the files are arranged?
4. Which data are calculated when needed?

Design and Analysis of Algorithm Page | 32

 Unit-I/Introduction

5. Algorithm Design Techniques

An algorithm design techniques or strategy or paradigm is general approach to solving

problems algorithmically that is applicable to a variety of problems from different areas of
computing.
Uses
 They provide guidance for designing algorithms or new problems.
 They provide guidance to problem which has no known satisfied algorithms.
 Algorithm design technique is used to classify the algorithms based on the design idea.
 Algorithm design techniques can serve as a natural way to categorize and study the
algorithms.

6. Methods of specifying an algorithm

 Natural Language- free style and step by step format

 Pseudocode- mixture of a natural language and programming language like constructs.
Pseudocode is usually more precise than natural language, and its usage often yields
more succinct algorithm descriptions.
 Flowchart - method of expressing an algorithm by a collection of connected
geometric shapes containing descriptions of the algorithm's steps.

7. Proving an Algorithm's correctness

 Once an algorithm has been specified, then its correctness must be proved.
 An algorithm must yield a required result for every legitimate input in a finite
amount of time.
 Mathematical Induction is a common technique used to prove the correctness of
the algorithm. In mathematical induction, an algorithm‟s iterations provide a natural
sequence of steps needed for proofs. If the algorithm is found incorrect, need to
redesign it or reconsider other decisions.

8. Analysing an algorithm

 Efficiency of an algorithm is determined by measuring the time, space and

amount of resources, it uses for executing the program.
 The efficiency of the algorithm is determined with respect to central processing
units time and internal memory.
 Efficiency of an algorithm

 Time efficiency (or) Time Complexity

 Space efficiency (or) Space Complexity

Design and Analysis of Algorithm Page | 33

 Unit-I/Introduction

Time efficiency (or) Time Complexity

 Time efficiency indicates how fast the algorithm runs.

 The time taken by a program to complete its task depends on the number of
steps in an algorithm.

Dependency Factors

Compilation Time Run Time (or) Execution Time

 The amount of time taken by  The execution time depends on

the compiler to compile an the size of the algorithm.
algorithm is known as
compilation time.  The execution time is
calculated for executable
 During compilation time, it statements and not for t h e
does not calculate the declaration statements.
executable statements, it
calculates only the declaration
statements and check for any
syntax and semantic errors.

Time Taken (T) by an algorithm = Compilation Time + Execution Time

Space efficiency

 Indicates how much extra memory the algorithm needs.

 There are three different space considered for determining the amount of memory
used by the algorithm.
 Instruction Space
When the program gets compiled, then the space needed to store the
compiled instruction in the memory is called instruction space.The
instruction space is independent of the size of the problem
 Data Space
The memory space used to hold the variables of data elements are called
data space.The data space is related to the size of the Problem.
 Environment Space
It is the space in memory used only on the execution time for each
Function call.It maintains runtime .stack in that it holds returning address
of the previous functions.

Design and Analysis of Algorithm Page | 34

 Unit-I/Introduction

 Simplicity Of An Algorithm

 Simplicity of an algorithm means generating sequence of instructions which are

easy to understand.
 While simplifying an algorithm we have to compute any predefined computations
or some complex mathematical derivation.
 Finding out bugs from algorithms or debugging the program becomes easy when
an algorithm is simple.

 Generality

 Generality shows that sometimes it becomes easier to design an algorithm in more

general way rather than designing it for particular set of input. Hence we should
write general algorithms always.
 For example, designing an algorithm for finding GCD of any two numbers is
more appealing than that of particular two values. But sometimes it is not all
required to design a generalized algorithm

9. Coding an Algorithm

 The implementation of an algorithm is done by suitable programming language.

 For example, C++ or JAVA.
 While writing a program for given algorithm it is essential to write an optimized
code. This will reduce the burden on compiler.

IMPORTANT PROBLEM TYPES

9. Explain the important problem types. [16M] (U)

Important Problem Types

Some of the most important problem types are

1. Sorting
2. Searching
3. String Matching (or) String processing
4. Graph Problems
5. Combinatorial problems
6. Geometric problems
7. Numerical Problems

1. Sorting

Problem Statement : Sorting means arranging the elements in increasing order or in

decreasing order.
Design and Analysis of Algorithm Page | 35
 Unit-I/Introduction

Problem Description:
Sorting .is the operation of arranging the records of a table according to the key value of the
each record.
Example : Sort student records in alphabetical order of names or by student number or by
student grade-point average(Key)

Applications: The sorting can be done on numbers, characters (alphabets), string or

employees record.

Properties of Sorting Algorithms

Stable
 A sorting algorithm is called stable, if it preserves the relative order of any two equal
elements in its input.
 In other words, if an input list contain two equal elements in positions i and j, where
i<j, then in the sorted list they have to be in position i' and j' respectively, such
that i' <j'
In-place
An algorithm is said to be in-place if it does not require extra memory, except, possibly
for a few memory units.

Selection Of A Sorting Method

1. Programming time. of the sorting algorithm.

2. Execution time of the program
3. Memory space needed for the programming environment

Design Of Sorting Algorithms

1. Minimum number of exchanges.

2. Large volume of data blocks movement.

Types of Sorting
Internal Sorting methods External Sorting methods

The key principle of internal sorting is The idea behind the external sorting is to
that all the data items to be sorted are move data from secondary storage to mail
retained in the main memory and random memory in large blocks for ordering the
access memory. data.

Examples Examples-Merge Sort.

1. Bubble sort
2. Selection sort
3. Shell. sort
4. Insertion sort
5. Quick sort
6. Heap sort

Design and Analysis of Algorithm Page | 36

 Unit-I/Introduction

2. Searching

Problem Statement : Searching is an activity by which we can find out the desired element
from the list. The element which is to be searched is called search key.
One of the important applications of array is searching
Searching Algorithm:
1. Sequential Search
2. Fibonacci search

3. String Processing

A string is a collection of characters from an alphabet.

Different types of strings
 Text string - collection of letters, numbers and special characters
 Bit string - collection of zeros and ones
Operations performed on a string
1. Reading and writing strings
2. String concatenation
3. Finding string length
4. String copy
5. String comparison
6. Substring operations
7. Insertions into a string
8. Deletions from a string
9. Pattern matching
Pattern Matching or String matching
The process of searching for an occurrence of word in a text is called Pattern matching.
Some of the algorithms used for pattern matching are
1. Simple pattern matching algorithm
2. Pattern matching using Morris Pratt algorithm
3. Pattern matching using Knuth-Morris-Pratt algorithm

4. Graph Problems

 Graph is a collection of vertices and edges.

 Formally, a graph G={ V, E }is defined by a pair of two sets.
V  Vertices
E  Edges.
 Types

Directed Graph - If the pairs of vertices are ordered, then G is called

a directed graph because every edge is directed
Undirected Graph - If the pair of the vertices are unordered then G is
called an undirected graph
.
Design and Analysis of Algorithm Page | 37
 Unit-I/Introduction

 Graph Problems
1. Graph Traversal Algorithms,
2. Shortest Path Algorithm
3. Topological Sorting.
4. Travelling Salesman Problem
5. Graph Colouring Problems

5. Combinatorial Problems
Problem Statement: A combinatorial object such as a permutation a combination or a subset
that satisfies certain constraints and has some desired property such as
maximizes a value or minimizes a cost .

Examples: Travelling Salesman Problem

Graph Colouring Problems .
Combinatorial problems are the most difficult problems-Reasons
1. As problem size grows the combinatorial objects grow rapidly and reach to huge
value.
2. There is no algorithms available which can solve these problems in finite amount of
time
3. Many of these problems fall in the category of unsolvable problem.

6. Geometric Problems

 Geometric algorithms deal with geometric objects such as points,lines and polygons.
 The procedure for solving a variety of .geometric problems includes the problems
of constructing simple geometric shapes such as triangles, circles.
 The two classic problems of computational geometry ate:
 Closest pair problem
Given n points in the plane, find the closest pair among them.
 Convex hull problem
Find the smallest-convex polygon that would include all the points of a
given set.
 The geometric problems are solved mainly in applications to computer
graphics or in robotics

7. Numerical problems

 Numerical problems are problems that involve mathematical objects of continuous

nature such as solving equations and systems of equations computing definite integrals
evaluating .
 Most of the mathematical problems can be solved by approximate algorithms.

Design and Analysis of Algorithm Page | 38

 Unit-I/Introduction

FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM

EFFICIENCY-ANALYSIS FRAMEWORK

10.Explain in detail about analysis framework. [16M] (R)

Analysis Framework

 Efficiency of an algorithm can be in terms of time or space.

 The performance of an algorithm is computed by two factors
 Amount of time required by an algorithm to execute
 Amount of storage required by an algorithm

Overview

1. Space complexity
2. Time complexity
3. Measuring an Input's size
4. Measuring Running Time
5. Orders of Growth

2. Space complexity

The space complexity can be defined as amount of memory required by an algorithm to

run.There are three different space considered for determining the amount of memory
used by the algorithm.
 Instruction Space
When the program gets compiled, then the space needed to store the
compiled instruction in the memory is called instruction space.The
instruction space is independent of the size of the problem
 Data Space
The memory space used to hold the variables of data elements are called
data space.The data space is related to the size of the Problem.
 Environment Space
It is the space in memory used only on the execution time for each
Function call.It maintains runtime stack in that it holds returning address
of the previous functions.
Factors for computing the space complexity - Constant and Instance characteristics.
Space requirement S(P) can be given as

S(p) = C+
Where C is a constant i.e. fixed part and it denotes the space of inputs and outputs.

Design and Analysis of Algorithm Page | 39

 Unit-I/Introduction

3. Time complexity

 The time complexity of an algorithm is the amount of computer time required

by an algorithm to run to completion.
 For instance in multiuser system, executing time depends on many factors such as
 System load
 Number of other programs running
 Instruction set used
 Speed underlying hardware
 The time complexity is therefore given in term of frequency count.
Frequency count count denoting number of times of execution of statement
Example
for (i=0; i<n; i++)
{
sum = sum + a[i];
}
Statement Frequency Count
i=0 1
i<n (n+1)-condition true, n times- condition false.
i++ n times
Sum=sum+a[i] n times
Total 3n+2

4. Measuring an Input's size

All algorithms run longer on larger inputs.

Examples
a. Evaluating a Polynomial
In problem of evaluating a polynomial p(x) = an X n + ....+ ao of degree n
Time Taken by the algorithm α degree or the number of its coefficients [Input Size]

b. In spell checking algorithm,

Time Taken by the algorithm α Number of characters/Words[Input Size]

Units for Measuring Running Time

 Some units of time measurement such as a second, a millisecond and so on can be
used to measure the running time of a program implementing the algorithm.
Drawbacks
1. Dependence on the speed of a particular computer
2. Dependence on the quality of a program implementing the algorithm.
3. The compiler used in generating the machine code.
4. The difficulty of clocking the actual running time of the program

Design and Analysis of Algorithm Page | 40

 Unit-I/Introduction

 Basic Operation

 The main objective is to identify the most important operation of the

algorithm, called the
 Basic Operation - the operation contributing the most to the total
running time

Running time α Number of times the basic operation is executed

Example
Most sorting algorithms work by comparing the elements (keys) of a list being .sorted
with each other. For. such algorithms the basic operation is a Key Comparison.

Computing execution time using basic operation

The formula to compute the execution time using basic operation is

T(n) ~ C(n)

Where
T(n) - running time
C(n) - no. of times this operation is executed.
Cop - execution time of algorithms basic operation.

4. Orders of Growth

Measuring the performance of an algorithm in relation with the input size „n‟ is called
order of growth.

N log n n log n n2 2n

1 0 0 1 2

2 1 2 4 4

4 2 8 16 16

Design and Analysis of Algorithm Page | 41

 Unit-I/Introduction

Classification Of Different Efficiency Classes.

 Constant
 Logarithmic
 Linear
 Quadratic
 Cubic
 Exponential
 Factorial
Properties Of Order Of Growth
 If F1 (n) is order of g1 (n) and F2 (n) is order of g2 (n), then
F1 (n) +F2 (n)  max g1 n, g 2 n .
 Polynomials of degree m  n m  .That means maximum degree is considered from the
polynomial.
 1  log n  n  n 2   2 n  .
Time Space Tradeoff
Time space tradeoff is basically a situation where either space efficiency (memory utilization)
can be achieved at the cost of time or time efficiency (performance efficiency) can be achieved
at the cost of memory.
Example:
Consider the programs like compilers in which symbol table is used to handle the variables and
constants. Now if entire symbol table is stored in the program then the time required for
searching or storing the variable in the symbol table will be reduced but memory requirement
will be more.

11. Explain how analysis of linear search is done with a suitable illustration.
[Nov2011-10M] (E)
Or
Write an algorithm for linear search and analyse the algorithm for its time
complexity. [May 2011 - 8M] (A)
Or
Analyse the best case, average and worst case analysis for linear search.•
[Dec 2012-8M] (A)
Or
Use the most appropriate notation to indicate the time efficiency class of sequential
search algorithm in the worst case, best case and the average case. [8M] [May 2016 ]
[Nov-2016] (E)

Worst Case, Best Case and Average Case efficiencies

The running time depends not only on an input size but also on the specifics of a particular
input.
Example: Sequential Search or Linear Search
Design and Analysis of Algorithm Page | 42
 Unit-I/Introduction

Problem Statement
To search for a given item using some search key K in a list of „n' elements by checking
successive elements of the list until a match with the search key is found or the list is
exhausted.

Worst case efficiency

The worst case efficiency of an algorithm is its efficiency for the worst case input of size n,
which is an input (or inputs) of size n. For which the algorithm runs the longest among all
possible of that size.

Determination of worst case efficiency of an algorithm

Analyse the algorithm to see what kind of inputs yield the largest value of the basic operations
count C(n) among all possible inputs -of size n.
For sequential search
Cworst (n)=n

Where n Number of inputs and hence n comparisons

ALGORITHM SequentialSearch(A[0..n - 1],K)

//Searches for a given value in a given array by sequential search
//Input: An array A[0..n - 1] and a search key K
//Output: The index of the first element in A that matches K
// or -1 if there are no matching elements
i ←0
while i<n and A[i] = K do
i ←i + 1
if i<n
return i
else
return -1

Best case efficiency

The best case efficiency of an algorithm is its efficiency for the best case input of size
n, which is an input (or inputs) of size n for which the algorithm runs the fastest among
all possible inputs of that size.
Determination of best case efficiency of an algorithm
 First, determine the kind of inputs of size n.
 Then ascertain the value of C(n) on these inputs.
For sequential search, the best case inputs will be lists of size 'n' with their first elements
equal to a search key.

Design and Analysis of Algorithm 1 Page | 43

 Unit-I/Introduction

Average case efficiency

It yields the necessary information about an algorithm's behaviour on a "typical"

or "random" input.

Determination of average case efficiency of an algorithm

To determine the algorithm's average case efficiency some assumptions about
possible inputs of size 'n'.
For Sequential Search
The average number of key comparisons Cavg (n) can be computed as follows:
Assumptions
(a) the probability of a successful search is equal to p (0 <p < 1)
(b) the probability of the first match occurring in the ith position of the list is the same
for every i.
 In .case of a successful search the probability of the first match occurring in the
position of the list is pin for every i. and the number. of comparisons made by the
algorithm in such a situation is obviously 'i'.
 In case of an unsuccessful search, the number of comparisons is 'n' with the
probability of such a search being (l-p).
Therefore,

Cavg (n) = p(n+1) + n(1-p)

2

Amortized Efficiency.

 It applies not to a single run of an algorithm but rather to a sequence of operations

performed on the same data structure.
 It turns out that in some situations a single operation can be expensive, but the total time
for an entire sequence of n such operations is always significantly better than the worst-
case efficiency of that single operation multiplied by n.
 So we can “amortize” the high cost of such a worst-case occurrence over the entire
sequence in a manner similar to the way a business would

U20IT303/Design and Analysis of Algorithm Page | 44

Unit-I/Introduction

ASYMPTOTIC NOTATIONS AND ITS PROPERTIES

12. Explain the Asymptotic Notations and its properties in detail? [May 2011-
8M](R)
(or)
Discuss in detail all the asymptotic notations with example. [May 2012 -16M] (R)
(or)
Distinguish between Big oh, Theta and Omega Notations.[Dec 2012-8M] (R)
(or)
Give the definition and Graphical representation of O-notations. [8M][May-
2016](R)

Asymptotic Notations

 Asymptotic notation is a shorthand way to represent the time complexity.

 Using asymptotic notations we can give time complexity as “fastest possible”, “slowest
possible” or “average time”.
 Various notations such as ,  and  used are called as asymptotic notations.

1. Big Oh Notation

The big Oh notation is denoted by „  ‟. It is a method of representing the upper bound of

algorithms running time. Let F(n) and g(n) be two non-negative functions. Let n0 and
constant c are two integers such that n0 denotes some values of input and n > n0. Similarly c
is some constant such that c > 0.

F n  c  g n

Then F(n) is big oh of g(n). It also denoted as F n  g n .

Example:
Consider a function F n  2n  2 and g n  n 2 . then we have to find some constant c,
so that F n  c * g n. as F n  2n  2 and g n  n 2 . then we find c for,

n=1

F n  2n  2  21  2

F n  4 and g n  n 2  12

g n  1

F n  g n
Page | 45
Unit-I/Introduction

If n = 2 then,

F n  2n  2  22  2  6

g n  2  4
2

g n  4

F n  g n

If n = 3 then

F n  2n  2  23  2  8

g n  3  9
2

F n  g n is true.

Hence we can conclude that for n > 2, we obtain F n  g n . Thus always upper bound of
existing time is obtained by big oh notation.

2. Omega Notation

A function F(n) is said to be in  (g(n)) if F(n) is bounded below by some positive constant
multiple of g(n) such that
F n  c  g n for all n  n0 .
It is denoted as F n  g n .

Example:

Consider F n  2n 2  5 and g n  7n.

If n = 0

F n  20  5  5
2

g n  70  0 i.e. F n  g n

Page | 46
Unit-I/Introduction

But if n = 1

F n  21  5  7
2

g n  71  7 i.e. F n  g n

If n = 3 then

F n  23  5  23
2

g n  73  21 i.e. F n  g n

Thus for n > 3 we get F n  c  g n .

It can be represented as

2n 2  5  n

3. Theta Notation

The theta notation is denoted by „  ‟. By this method the running time is between upper bound
and lower bound. Let F(n) and g(n) be two non-negative functions. There are two positive
constants namely c1 and c2 such that,

o c1 g (n)  F n  c2 g n .

o Then we can say that F n  g n .

Example:

If F n  2n  8 and g n  7n.

If n = 1 then

F n  21  8  10

g n  7(1)  7

5n  2n  8  7n For n  2

Here c1  5 and c2  7 with n0  2.

Page | 47
Unit-I/Introduction

MATHEMATICAL ANALYSIS FOR RECURSIVE AND NON-RECURSIVE

ALGORITHMS.

13. State the general plan for analysing the time efficiency of non-recursive
algorithms and explain with an example.[16M] [Nov-2016] (U)
or
Define recurrence equation and explain how solving recurrence equations are
done. [Nov 2011 - 6M](U)

Recurrence Relation

The recurrence relation can be solved by following methods:

a. Substitution method
b. Masters method

Substitution Method

In substitution method a guess for solution is made. There are two types of
substitution:

 Forward substitution
 Backward substitution

Forward substitution:

In this method makes use of an initial condition in the initial term and value for the
next term is generated. This process is continued until some formula is guessed.

Example:

Consider a recurrence relation

T n  T n  1  n with initial condition T 0  0.

Let,

T n  T n  1  n …………………………… (1)

Page | 48
Unit-I/Introduction

If n = 1 then

T 1  T 0  1  0  1

T 1  1 ………………………….. (2)

If n = 2 then

T 2  T 1  2  1  2

T 2  3 ………………………….. (3)

If n = 3 then

T 3  T 2  3  3  3

T 3  6 ………………………….. (4)

By observing above generated equations we can derive a formula

nn  1 n 2 n
T n    
2 2 2

We can also denote T n  in terms of big oh notation as follows-

 
T n   n 2

Backward substitution:

In this method backward values are substituted recursively in order to derive some
formula.

Consider a recurrence relation

T n  T n  1  n …………………. (1)

With initial condition T 0  0.

T n  1  T n  1  1  n  1 ………………….. (2)

Putting equation (2) in equation (1) we get,

T n  T n  2  n  1  n ……………………. (3)

Page | 49
Unit-I/Introduction

Let

T n  2  T n  2  1  n  2 …………... (4)

Putting equation (4) in equation (3) we get,

T n  T n  3  n  2  n  1  n

………….

T n  T n  k   n  k  1  n  k  2  n.....  n

If k = n then

T n  T 0  1  2  ....n

T n  0  1  2  ....n

nn  1 n 2 n
T n    
2 2 2

We can also denote T n  in terms of big oh notation as follows-

T n   n 2  
Masters Method:

Consider a recurrence relation

T n  aT a / b  f n

We will map this equation with

T n  aT n / b  f n

Now f n  is n. n1 .hence d = 1

a = 4 and b = 2 and
a  b d i.e. 4 > 2
1


T n   n logb a 
 
T n   n log2 4

T n  n  2
 log 2 4  2

Hence time complexity is T n  n 2  .

Page | 50
Unit-I/Introduction

PART – C
ASYMPTOTIC NOTATIONS AND ITS PROPERTIES

1. Give the Algorithm to check whether all the elements in a given array of n
elements are distinct. Find the worst case complexity of the
same.[8M][May2016] (C)

Algorithm Unique_Elements (A [0….. n-1])

for i  0 to n-2 do
{
for j  i+1 to n-1 do
{
if(A[i]=A[j]) then
return false
}
}
return true
Mathematical Analysis

i. The input size is n i.e. total number of elements in array A.

ii. The basic operation will be comparison of two elements. This operation is the
innermost operation in the loop. Hence if(A[i]=A[j]) will be the basic
operation.
iii. The number of comparisons made will depend upon the input n.
iv. The worst case input is when we require largest number of comparisons for the
array of size n. The worst case time is denoted by Cworst(n).

We can obtain Cworst(n) as-

C worst n  Outer loop  Inner loop

n2 n 1
C worst n   1
i 0 j  i 1

Now we will simplify C worst as follows-

n 1
 n 
1  n  1  i  1  1
j i 1
1  n  k  1 is the rule.
 i k 
n2 n2 n2
=  n  1  i 
i 0
=  n  1   i
i 0 i 0

Now taking (n-1) as a common factor, we can write

= n  11 
n2
n  2n  1 this can be obtained using formula
i 0 2
Page | 51
 Unit-I/Introduction

n
nn  1
i 
i 1 2
n

n  2n  1 1  n  1  1  n
= n  1n  1  i 1
n2
2
1  n  2  0  1  n  1
i 0

Solving this equation we will get

2n  1n  1  n  2n  1
=
2
=
  
2 n  2n  1  n 2  3n  2
2

2
=

n n
2

2
1
= n2
2
Thus the time complexity of the above algorithm is n 2 .

2. Derive the worst case analysis of Merge sort with suitable illustration. [8M]
[May/June 2015] (AP)

Merge Sort

Merge sort is a perfect example of a successful application of the divide and conquer technique.
It sorts a given array A[0...n-l] by dividing it into two halves

A [0... [n /2 ] - 1] and A [[n/2]....n-l], s

Sorting each of them recursively, and then merging the two smaller sorted arrays into a single
sorted one.

ALGORITHM Mergesort(A[0..n − 1])

//Sorts array A[0..n − 1] by recursive mergesort
//Input: An array A[0..n − 1] of orderable elements
//Output: Array A[0..n − 1] sorted in nondecreasing order
if n > 1
copy A[0.._n/2_ − 1] to B[0.._n/2_ − 1]
copy A[_n/2_..n − 1] to C[0.._n/2_ − 1]
Mergesort(B[0.._n/2_ − 1])
Mergesort(C[0.._n/2_ − 1])
Merge(B, C, A)

The merging of two sorted arrays can be done as follows. Two pointers (array indices) are
initialized to point to the first elements of the arrays being merged. The elements pointed to are
compared, and the smaller of them is added to a new array being constructed; after that, the
index of the smaller element is incremented to point to its immediate successor in the array it

CS6402/Design and Analysis of Algorithm Page | 52

Unit-I/Introduction

was copied from. This operation is repeated until one of the two given arrays is exhausted, and
then the remaining elements of the other array are copied to the end of the new array.

ALGORITHM Merge(B[0..p . 1], C[0..q . 1], A[0..p + q . 1])

//Merges two sorted arrays into one sorted array
//Input: Arrays B[0..p . 1] and C[0..q . 1] both sorted
//Output: Sorted array A[0..p + q . 1] of the elements of B and C
i ←0; j←0; k←0
while i <p and j <q do
if B[i]. C[j ]
A[k] ←B[i]; i←i + 1
else A[k] ←C[j ]; j←j + 1
k←k + 1
if i = p
copy C[j..q . 1] to A[k..p + q . 1]
else copy B[i..p . 1] to A[k..p + q . 1] (4)

(3)
Complexity

Simplicity that n is a power of 2, the recurrence relation for the number of key comparisons
C(n) is
 C(n) = 2C(n/2) + Cmerge(n) for n > 1, C(1) = 0.

Page | 53
Unit-I/Introduction

In the worst case, neither of the two arrays becomes empty before the other one contains just
one element (e.g., smaller elements may come from the alternating arrays). Therefore, for
the worst case, Cmerge(n) = n − 1, and the recurrence
 Cworst(n) = 2Cworst(n/2) + n − 1 for n > 1, Cworst(1) = 0.

Hence, according to the Master Theorem, Cworst(n) ∈ Θ(n log n) (why?). In fact, it is easy
to find the exact solution to the worst-case recurrence for n = 2k:
Cworst(n) = n log2 n − n + 1.

3. Write the insertion sort algorithm and estimate the running time. [8M]May/June
2015 (AP)

Insertion Sort Algorithm

It is a simple Sorting algorithm which sorts the array by shifting elements one by one.
Following are some of the important characteristics of Insertion Sort.

1. It has one of the simplest implementation

2. It is efficient for smaller data sets, but very inefficient for larger lists.
3. Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially
sorted list, hence it increases its efficiency.
4. It is better than Selection Sort and Bubble Sort algorithms.
5. Its space complexity is less, like Bubble Sorting, inerstion sort also requires a single
additional memory space.
6. It is Stable, as it does not change the relative order of elements with equal keys

INSERTION_SORT (A)
for j ← 2 to length[a]
do key ← a[j]
{put a[j] into the sorted sequence a[1 . . j − 1]}
i←j−1
while i > 0 and a[i] > key
do a[i +1] ← a[i]
i←i−1
a[i + 1] ← key

Running Time of Algorithm

The running time of an algorithm for a specific input depends on the number of operations
executed. The greater the number of operations, the longer the running time of an algorithm
Average complexity=Θ(N2)

Page | 54
Unit-I/Introduction

4. Solve the given recurrence relation using recursion tree, T n   2T    n and

n
2
T 1  1 . [16M] (AP)

Solution

Step 1: Step 2: Step 3:

T n  n n n

Step 4

n n

..............n

..............n

After certain steps we will get

N n

Page | 55
Unit-I/Introduction

The depth of the tree is log n. hence we can guess that, total cost= n log n T (1). Hence we get
the overall cost as n log n .

5. Solve the recurrence relation T n   3T    Cn 2 using tree method. [16M] (AP)

n
4

Solution
Cn2

.
.

………………………………………….
n n
Thus size for a node at depth i is
i
. If n = 1 the i =1. Hence n=4i. Hence log 4 n  i. thus
4 4
2
n
depth i= (0, 1, 2,……..+ log 4 n  1 ) = log 4 n  1 and cost of each node is C  i  .
4 

Page | 56
 Unit-I/Introduction

2
i n
 3 C  i  is overall cost =
3
 
C n2 . The last level at depth log 4 n has
4  16
3 log4 n
 
 n log4 3   n log4 3 .

(i) Solve the recurrence relation T n   T    T    n   .... using the tree
n 2n
6.
3  3 
method. [8M] (AP)

Solution
N n

log 3 / 2 n

The longest path from root to a leaf is

2
2 2
n   n    n  ....  1
3 3
k
2
  n 1
3
If we assume k  log 3 / 2 n. then the height of the tree is log 3 / 2 n .
The solution to recurrence = number of levels * cost of each level. T n  n log n .

4. (ii). If T1n   f n and T2 n  g n then show that
T1n  T2 n  max  f n, g n . [8M] (AP)

Solution

Let there be some constant c1 such that

T1 n  c1 g1 n for n  n1 …………………. (1)

Similarly there will be some constant c 2 such that

Page | 57
Unit-I/Introduction

T2 n  c2 g 2 n for n  n2 …………………. (2)

Let c3  max c1 , c2 such that n  max n1 , n2 

Then we can write using equation (1) and (2) as:

T1 n  T2 n  c1 g1 n  c2 g 2 n

 c1  c2 g1 n  g 2 n

 c3 g1 n  g 2 n

 c3 max g1 n  g 2 n

Hence
T1 n  T2 n  max g1 n  g 2 n is true.

MATHEMATICAL ANALYSIS FOR RECURSIVE AND NON-

RECURSIVE ALGORITHMS.

5. Explain various methods used for solving Fibonacci series and calculate
their efficiencies. [16M] (A)

Fibonacci series

Step 1: The Fibonacci series algorithm works for input size n.

Step 2: The basic operation in computing Fibonacci is multiplication.
Algorithm fib (n)
if (n=1)||(n=2)
return 1
else
return (fib(n-1)+fib(n-2))

Mathematical Analysis

The recursive function call can be formulated as

T n  2T n  1  1 where n > 0

With initial condition T 0  0

Solution:

T n  2T n  1  1

Page | 58
Unit-I/Introduction

T n  22T n  2  1  1

T n  42T n  3  1  1  2

T n  2 k T n  k   2 k

T n  2 n T n  n  2 n where k = n

T n  2 n T 0  2 n

T n  0  2 n where T 0  0

T n  2 n

Thus the time complexity of Fibonacci algorithm is 2 n .

6. Find the time complexity and space complexity Factorial using recursion and
compare nth Fibonacci number using Iterative statements.[Dec 2012-
8M](A)

Factorial

The factorial of some number can be obtained by performing repeated multiplication.

For instance: if n = 5 then

Step 1: n! = 5!

Step 2: 4!*5

Step 3: 3!*4*5

Step 4: 2!*3*4*5

Step 5: 1!*2*3*4*5

Step 6: 1*1*2*3*4*5

Page | 59
Unit-I/Introduction

The above mentioned steps can be written in pseudo code as-

Algorithm Factorial (n)

if(n=0)
return 1
else
return Factorial (n-1) *n

Mathematical Analysis

Step 1: The factorial algorithm works for input size n.

Step 2: The basic operation in computing factorial is multiplication.

Step 3: The recursive function call can be formulated as

F n  F n  1 * n where n > 0

Then the basic operation multiplications is given as M n  .

M n  M n  1  1

Solution

M n  M n  1  1
= M n  2  1  1  M n  2  2
= M n  3  1  1  1  M n  3  3
From the substitution methods we can establish a general formula as:
M n  M n  i   i
Put i=n
M n  M 0  n
Hence M n  n
Thus the time complexity of factorial function is n .

7. Solve recurrence relation T n   k.T    n 2 when T 1  1 , and k is any constant.

n
k
[8M] (AP)

Solution

n
T n   k .T    n 2 be a recurrence relation.
k

If we assume k = 2 then the equation becomes

Page | 60
 Unit-I/Introduction

2
n
T n   2T    n 2 where T    2T     
n n n
2 2 4 2

 n n2 
= 22.T      n 2
 4 4 

n n2
= 4T     n2
4 2

2
 n  3n
where T    2T     
2
n n n
= 4T   
4 2 4 8 4

  n  n 2  3n 2
= 42.T     
  8  16  2

n n 2 3n 2
= 8T    
8 4 2

n 7n 2
= 8T   
8 4

 n  2 1 2
k
= 2k T    k 1
n
2  2
k

2k  1
= 2 T  k   Cn 2
n
k
 k 1  C  Constant
2  2

n
If we put  1 then 2 k  n and k  log 2 n
2k

= nT 1  Cn 2

= n  Cn 2

T n  = n 2

U20IT303OIT303/Design and Analysis of Algorithm Page | 61

 Unit-I/Introduction

8. Solve the following recurrence relation using master theorem, (AP)

a.
 2  n 2
T n   8T n [8M]

T n   9T n   n 3
[8M]
b. 3

a.  2  n
T n   8T n 2

Solution

Here f n  n 2

a  8, b  2

 log 2 8  3

Then according to case 1 of master theorem


f n   n logb a  

f n   n log2 8 
= n 3  If we put   1 then n 3  1  n 2   f n

Then T n  = n log b a


T n  = n log2 8 

T n  = n 3 

b.  3  n
T n   9T n 3
(8)

Solution

Here a = 9, b = 3 and f n  n 3

And log 3 9  2

According to case 3 in master theorem

As f n  is n log 9  3


f n   n 2  and we have f n  n 3

U20IT303/Design and Analysis of Algorithm Page | 62

 Unit-I/Introduction

Then to have f n  n we must put   1 .

Then T n   f n

T n   n 3  

9. Solve the following recurrence relation using master theorem, (AP)

a.
 2  1
T n   T n [8M]

T n   9T n   n [8M]
b. 3

 
a. T n  T n 2  1

Solution

Here a = 1 and b = 2.
And log 2 1  0 now we will analyze f n  1 .

We assume f n  2 k

When k = 0 then f n  2 0  1.

That means according to case 2 in master theorem.

 
f n   n logb a log k n

f n  n log n

log2 1 0

f n  n .1 0

f n  1  n0  1


 We get T n   n logb a log k 1 n 
 
T n   n log2 1 log 01 n

T n  n . log n

0 1

T n  log n  n0  1

 
b. T n  9T n 3  n (8)

Solution
Here a = 9, b = 3 and f n  n

n logb a  n log3 9  n 2

U20IT303/Design and Analysis of Algorithm Page | 63

 Unit-I/Introduction

Now f n  n

  
T n  f n   n logb a    n 2 
When   1 . That means case 1 is applicable. According to case 1, the time
complexity of such equation is

 
T n   n logb a

T n  n  log3 9

T n  n  2

Hence the complexity of given recurrence relation is n 2 .

10.Obtain Matrix Multiplication and Analyze the Efficiency using non-recursive

algorithm. [16M] (AP)

Matrix Multiplication

Algorithm matrix_mul (A [0….n-1, 0…. n-1], B [0….n-1, 0…. n-1]

for i  0 to n-1 do
for j  0 to n-1 do
C [i, j]  0
for k  0 to n-1 do
C [i, j]  C [i, j] +A [i, k]*B [k, j]
return C

Mathematical Analysis

i. The input size of above algorithm is simply order of matrices n.

ii. The basic operation is in the innermost loop and which is C [i, j] 

C [i, j] +A [i, k]*B [k, j]

iii. The basic operation depends only upon input size.

Then the basic operation multiplication is given as M n  .

 M n  Outermost loop  Inner loop  Innermost loop (1 execution)

= [For loop using i]  [For loop using j]  [For loop using k](1 execution)

n 1 n 1 n 1
M n    1
i 0 j 0 k 0

U20IT303/Design and Analysis of Algorithm Page | 64

 Unit-I/Introduction

n 1 n 1
M n    n
i 0 j 0

n 1
M n   n2
i 0

M n  n3

Thus the simplified sum is n3. Thus the time complexity of matrix multiplication
 
 n3 .

11. Find whether all the elements in an array are distinct and analyze the efficiency
using non-recursive algorithm. [16M] (AP)

Algorithm Unique_Elements (A [0….. n-1])

for i  0 to n-2 do
{
for j  i+1 to n-1 do
{
if(A[i]=A[j]) then
return false
}
}
return true

Mathematical Analysis

v. The input size is n i.e. total number of elements in array A.

vi. The basic operation will be comparison of two elements. This operation is the
innermost operation in the loop. Hence if(A[i]=A[j]) will be the basic
operation.
vii. The number of comparisons made will depend upon the input n.
viii. The worst case input is when we require largest number of comparisons for
the array of size n. The worst case time is denoted by Cworst(n).

We can obtain Cworst(n) as-

C worst n  Outer loop  Inner loop

n2 n 1
C worst n   1
i 0 j  i 1

U20IT303/Design and Analysis of Algorithm Page | 65

 Unit-I/Introduction

Now we will simplify C worst as follows-

n 1
 n 
1  n  1  i  1  1
j i 1
1  n  k  1 is the rule.
 i k 

n2
=  n  1  i 
i 0

n2 n2
=  n  1   i
i 0 i 0

Now taking (n-1) as a common factor, we can write

= n  11 
n2
n  2n  1 this can be obtained using formula
i 0 2

n
nn  1
i 
i 1 2

n  2n  1 1  n  1  1  n
= n  1n  1  i 1
n2
2
1  n  2  0  1  n  1
i 0

Solving this equation we will get

2n  1n  1  n  2n  1

=
2

=
  
2 n 2  2n  1  n 2  3n  2 
2

=
n 2
n 
2

1 2
= n
2

Thus the time complexity of the above algorithm is n 2 .

U20IT303/Design and Analysis of Algorithm Page | 66

 Unit-I/Introduction

12. Find the element with maximum value in a given array and analyze the
efficiency of an algorithm using non-recursive method. [16M] (AP)

Algorithm Max_Elements(A[0…..n-1])
Max_value  A[0]
for i  1 to n-1 do
{
if(A[i]>Max_value) then
Max_value  A[i]
}
return Max_value

Mathematical Analysis

i. The input size is n i.e. total number of elements in array.

ii. The basic operation is comparison in loop for finding larger value.
iii. The comparison is executed on each repetition of the loop.
iv. Let C(n) be the number of times the comparison is executed. The algorithm
makes comparison each time the loop executes. That means with each new
value of i the comparison is made. Hence for i=1 to n-1 times the comparison
is made. Therefore we can formulate C(n) as-

C(n) = One comparison made for each value of i

Lets us simplify the sum

n 1
C n   1
i 1

n
C n  n  1  n [Using the rule 1  n  n  ]
i 1

Thus the efficiency of above algorithm is n 

Design and Analysis of Algorithm Page | 67

Unit-V/Coping with the Limitations of Algorithm Power

Page 68