DESIGN AND ANALYSIS OF ALGORITHMS

(Integrated)
22CSE43
MODULE 1

• Introduction: Notation of algorithm,

Fundamentals of Algorithmic Problem Solving,
Fundamentals of the Analysis of Algorithmic
Efficiency: Analysis framework, Asymptotic
Notations and Efficiency Classes, Mathematical
Analysis of Non-recursive and Recursive
Algorithms.
• Brute Force: Selection Sort and Bubble Sort
What is an Algorithm?
• A sequence of unambiguous instructions for solving a
problem, that is for obtaining the required output for any
legitimate input in a finite amount of time.

• An algorithm is a finite set of instructions that, if followed,

accomplishes a particular task.
Euclid’s algorithm for computing
gcd(m, n)
• Step 1 If n = 0, return the value of m as the answer and stop; otherwise,
proceed to Step 2.

• Step 2 Divide m by n and assign the value of the remainder to r.

• Step 3 Assign the value of n to m and the value of r to n. Go to Step 1.

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 not equal to 0 do
r ← m mod n
m←n
n←r
return m
Algorithm for calculate factorial value of a number :
[algorithm to calculate the factorial of a number]
•step 1. Start
•step 2. Read the number n
•step 3. [Initialize]
• i=1, fact=1
•step 4. Repeat step 4 through 6 until i=n
•step 5. fact=fact*i
•step 6. i=i+1
•step 7. Print fact
•step 8. Stop
[process finish of calculate the factorial value of a number]
• ALGORITHMSieve(n)
//Implements the sieve of Eratosthenes
//Input: A positive integer n>1
//Output: Array L of all prime numbers less than or equal to n
for p ←2tondoA[p]←p for p ←2to √n do
//seenotebeforepseudocode if A[p]= 0 / j ← p∗p while j ≤
ndo A[j]←0 //markelementas eliminated j ←j+p //copy the
remaining elements of A to array L of the primes i ←0 for p
←2tondo if A[p]= 0 L[i]←A[p] i ←i+1 return L
Fundamentals of Algorithmic Problem Solving

A sequence of steps required in designing and analyzing an algorithm

• Understand the problem

• Ascertain the capability of a computational Device
• Choosing between Exact and Approximate problem-solving
• Algorithm design techniques
• Designing an algorithm and Data Structures
• Proving an Algorithm’s Correctness
• Analyzing an Algorithm
• Coding an Algorithm
Understand the problem

• The first thing need to do before designing an algorithm is to understand

completely the problem given.

• Read the problem’s description carefully and ask questions if you have any
doubts about the problem.

• Do a few small examples by hand, think about special cases, and ask
questions again if needed.
• If the problem in question is one of them, then able to use a known
algorithm for solving it.

• Of course, it helps to understand how such an algorithm works and to know

its strengths and weaknesses, especially if you have to choose among
several available algorithms.
• 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.

If we fail to do this, algorithm may work correctly for a majority of inputs but
crash on some “boundary” value. Remember that a correct algorithm is not
one that works most of the time, but one that works correctly for all
legitimate inputs
Ascertain the capability of a computational Device
• How the objects would be represented?

• Is it a RAM model or concurrent execution?

• How the operations would be implemented?

• Is it a sequential algorithm or a parallel Algorithm?

Choosing between Exact and Approximate
problem solving
• First, there are important problems that simply cannot be solved
exactly for most of their instance.

• Problems like extracting square roots, solving non-linear equations,

and evaluating definite Integrals can not be solved exactly for most
of the instances

• Solving some problems for exact results can be unacceptably slow

because of the intrinsic complexity of the problem.
Algorithm design Techniques

•It is a general approach to solving problems algorithmically that

applies to a variety of problems from different areas of computing.

•They guide designing algorithms for new problems.

•It makes it possible to classify the algorithms according to an

underlying design idea which serves as a natural way to categorize
and study algorithm
Algorithm design techniques

:
• Design an algorithm Build a computational model of the solving process
and specify it in some fashion

• Methods of specifying an algorithm

• Using Natural Language
• Using Pseudocode
• Flowchart
Prove correctness
• The algorithm should yield the required output for every legitimate input
in a finite amount of time.

• The technique used for proving correctness is mathematical induction

• Tracing the algorithm’s performance for a few specific legitimate input

• If the algorithm is found to be incorrect, either redesign it or reconsider

one or more of those decision

• For the approximation algorithm the error produced by the algorithm does
not exceed a predefined limit
Analyze the algorithm
• Time Efficiency: How fast the algorithm is?

• Space Efficiency: How much memory does the extra

algorithm need?

• Simplicity: Easy to understand and to program

• Generality: range of inputs, special cases

• Optimality: No other algorithm can do better

Coding an Algorithm
• How the objects and operations in the algorithm are
represented in the chosen programming language?

• Validity of the program is established by testing.

• Note: Implementing the algorithm correctly is necessary but not

sufficient, it should be efficient

• As a rule, a good algorithm is a result of repeated effort and rework.

• Inventing algorithm is very creativeand rewarding process
Important Problem Types,
• Sorting
• Searching
• String processing
• Graph problems
• Combinatorial problems
• Geometric problems
• Numerical problem
Algorithm Specification
An algorithm can be specified in
1)Simple English

2)Graphical representation like flow chart

3)Programming language like c++ / java

4) Combination of above methods.

• Using the combination of simple English and C++, the
algorithm for selection sort is specified as follows
Performance Analysis: Space
complexity
• The total amount of computer memory required by an
algorithm to complete its execution is called as space
complexity of that algorithm. The Space required by an
algorithm is the sum of the following components

• A fixed part that is independent of the input and output.

This includes memory space for codes, variables,
constants, and so on.
• A variable part that depends on the input, output and
recursion stack. ( We call these parameters as instance
characteristics)

• Space requirement S(P) of an algorithm P,

S(P) = c + Sp
where c is a constant depends on the fixed part, Sp is
the instance characteristics
• Memory is required for the following
purposes:
1. To store program instruction
2. To store a constant value
3. To store variable value
4. For a few other things like function calls,
jumping statements, etc.
• Example-1: Consider following algorithm abc()

float abc (float a, float b, float c)

{
return(a+b+b*c + (a+b-c)/(a+b) + 4.0);
}
Here fixed component depends on the size of a, b and c.
Also instance characteristics Sp=0
• Example-2: Let us consider the algorithm to find sum of
array.
For the algorithm given here the problem instances are characterized
by n, the number of elements to be summed. The space needed by
a[ ] depends on n. So the space complexity can be written as;
Ssum(n) ≥ (n+3) n for a[ ], One each for n, i and s.
Performance Analysis: Time complexity
• The execution time or run-time of the program is
refereed as its time complexity denoted by tp (instance
characteristics). This is the sum of the time taken to
execute all instructions in the program.

• Time Complexity depends on following factors

System Load
Number of other programs running
Instruction set
Speed of underling hardware
• The time complexity is given in terms of frequency count.

• The frequency count is a count that denotes how many

times a particular statement is executed.
Asymptotic Notations
• Asymptotic Notation is a way to represent
the time complexity
• Asymptotic notation is a way of comparing
functions that ignores constant factors and
small input sizes.
Asymptotic Notations
• The core logic of an algorithm is called a
basic operation.
• Measuring the performance of an
algorithm in relation to the input size n is
called the Order of Growth.
• Three notations used to compare orders of
growth of an algorithm‘s basic operation
count are:
O, Ω, Θ notations
Big Oh- O notation
• The Big oh notation is denoted by ‘O’

• It is a method of representing the upper

bound of the algorithm running time.

• The big oh notation gives the longest

amount of time taken by the algorithm to
complete.
Big Oh- O notation
• A function t(n) is said to be in O(g(n)), denoted t(n)=O(g(n)), if t(n) is bounded
above by some constant multiple of g(n) for all large n, i.e., if there exists some
positive constant c and some nonnegative integer n0 such that
• t(n) ≤ cg(n) for all n ≥ n0
Omega Notation
• Omega notation is denoted by Ω.

• This notation is used to represent the lower bound of

the algorithm’s running time.

• The Omega notation gives the shortest amount of

time taken by the algorithm.
Omega Notation
A function t (n) is said to be in Ω (g(n)), denoted t(n) = Ω (g (n)), if t (n) is bounded
below some constant multiple of g (n) for all large n, i.e., if there exists some positive
constant c and some nonnegative integer n0 such that

t(n) ≥ cg(n) for all n ≥ n0

Big Theta- Θ notation
• A function t (n) is said to be in Θ(g (n)), denoted t(n) = Θ(g (n)), if t (n) is
bounded bot h above and below by some constant multiple of g (n) for all large n,
i.e., if there exist some positive constant c1 and c2 and some nonnegative integer
n0 such that
c2 g (n) ≤ t (n) ≤ c1 g (n) for all n ≥ n0
Class Name Comments

1 constant Short of best-case efficiencies, very few reasonable examples can be given since an
algorithm’s running time typically goes to infinity when its input size grows infinitely
large.

log n logarithmic Typically, a result of cutting a problem’s size by a constant factor on each iteration of
the algorithm (see Section 4.4). Note that a logarithmic algorithm cannot take into
account all its input or even a fixed fraction of it: any algorithm that does so will have
at least linear running time.

n linear Algorithms that scan a list of size n (e.g., sequential search) belong to this class.

n log n linearithmic Many divide-and-conquer algorithms (see Chapter 5), including mergesort and
quicksort in the average case, fall into this category.
Mathematical analysis of Non-Recursive algorithms

•General plan for analysing efficiency of non-recursive algorithms:

1. Decide on parameter n indicating input size
2. Identify the algorithm‘s basic operation
3. Check whether the number of times the basic operation is executed depends
only on the input size n. If it also depends on the type of input, investigate worst,
average, and best case efficiency separately.
4. Set up a summation for C(n) reflecting the number of times the algorithm‘s
basic operation is executed.
5. Simplify summation using standard formulas
Example: Finding the largest element in a given array
ALOGORITHM MaxElement(A[0..n-1])
//Determines the value of largest element in a given array
//nput: An array A[0..n-1] of real numbers
//Output: The value of the largest element in A
currentMax ← A[0]] [Pick the date
] for i ← 1 to n - 1 do
if A[i] > currentMaxPick the date]

currentMax ← A[i]
return currentMax
• Analysis:
1. Input size: number of elements = n (size of the array)
2. Basic operation:
a) Comparison
b) Assignment
3. No best, worst, average cases
4. Let C (n) denotes number of comparisons: Algorithm makes one comparison on
each execution of the loop, which is repeated for each value of the loop‘s variable
i within the bound between 1 and n – 1.
Example: Element uniqueness problem
Algorithm UniqueElements (A[0..n-1])
//Checks whether all the elements in a given array are distinct
//Input: An array A[0..n-1]

//Output: Returns true if all the elements in A are distinct and false otherwise

for i <-0 to n - 2 do {
for j <---i + 1 to n – 1 do {
if A[i] = = A[j]
return false
}}
return true
Analysis
1. Input size: number of elements = n (size of the array)
2. Basic operation: Comparison
3. Best, worst, average cases EXISTS.
Worst case input is an array giving largest comparisons.
• Array with no equal elements
• Array with last two elements are the only pair of equal elements
4. Let C (n) denotes number of comparisons in worst case: Algorithm makes one
comparison for each repetition of the innermost loop i.e., for each value of the
loop‘s variable j ranging from i + 1 to n – 1; and this is repeated for each value
of the outer loop i.e, for each value of the loop‘s variable i between its
limits 0 and n – 2
Mathematical analysis of Recursive algorithms
• General plan for analysing efficiency of recursive algorithms:
1. Decide on parameter n indicating input size
2. Identify the algorithm‘s basic operation
3. Check whether the number of times the basic operation is executed depends only on
the input size n. If it also depends on the type of input, investigate worst, average,
and best case efficiency separately.
4. Set up recurrence relation, with an appropriate initial condition, for the number of
times the algorithm‘s basic operation is executed.
• 5. Solve the recurrence.
Recurrence Relation
• The recurrence equation is an equation that defines a
sequence recursively.

• It is in the form of
T(n)=T(n-1)+n for n>0 -------(1)
T(0)=0 -------(2)

• Equation (1) is called recurrence relation.

• Equation(2) is called initial condition.
Solving Recurrence Equations
• There are 2 methods for solving the
recurrence equation
Substitution method
Master’s Method
• Substitution methods are of two types
Forward Substitution
Backward Substitution
Master’s Method
Let a ≥ 1 and b > 1 be constants, let f(n) be a
function, and let T(n) be a function over the positive
numbers
defined by the recurrence

T(n) = aT(n/b) + f(n).

If f(n) = Θ(nd), where d ≥ 0, then

•T(n) = Θ(nd) if a < bd,
•T(n) = Θ(ndlog n) if a = bd,
•T(n) = Θ(nlogba) if a > bd.
T(n) = aT(n/b) + f(n) where, T(n) has the following
asymptotic bounds:

1.If f(n) = O(nlogb a-ϵ), then T(n) = Θ(nlogb

a
).

2. If f(n) = Θ(nlogb a log n^k),

then T(n) = Θ(nlogb a * log n)

3. If f(n) = Ω(nlogb a+ϵ),

then T(n) = Θ(f(n)). ϵ > 0 is a constant.
Example: Factorial function
ALGORITHM Factorial (n)
//Computes n! recursively
//Input: A nonnegative integer n
[ick] //Output: The value of n!
if n = = 0
the date]

return 1
else
return Factorial (n – 1) * n
1. Input size: given number = n
2. Basic operation: multiplication
3. NO best, worst, average cases.
4. Let M (n) denote the number of multiplications.
M (n) = M (n – 1) + 1 for n > 0
M (0) = 0 initial condition
Where: M (n – 1) : to compute Factorial (n – 1)
1 : to multiply Factorial (n – 1) by n
5. Solve the recurrence: Solving using the “Backward substitution method”:
M (n) = M (n – 1) + 1
= [ M (n – 2) + 1 ] + 1
= M (n – 2) + 2
= [ M (n – 3) + 1 ] + 3
= M (n – 3) + 3
…
In the ith recursion, we have
= M (n – i ) + i
When i = n, we have
= M (n – n ) + n = M (0 ) + n
Since M (0) = 0
=n M (n) = Θ (n)
Example: Find the number of binary digits in the binary representation of a
positive decimal integer
ALGORITHM BinRec (n)
//Input: A positive decimal integer n
//Output: The number of binary digits in n‟binary representation
if n = = 1
return 1
else
return BinRec (└ n/2 ┘) + 1