Module-1

Analysis & Design of Algorithms(BCS401)

By :
Vishal Sathawane
Assistant Professor
Department of Computer Science and Engineering
Module-1
Syllabus:-
✔ INTRODUCTION: What is an Algorithm?, Fundamentals of Algorithmic Problem Solving.
✔ FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM EFFICIENCY: Analysis Framework,
Asymptotic Notations and Basic Efficiency Classes, Mathematical Analysis of Non
recursive Algorithms, Mathematical Analysis of Recursive Algorithms.
✔ BRUTE FORCE APPROACHES: Selection Sort and Bubble Sort, Sequential Search and Brute
Force String Matching.

Text Book:
✔ Introduction to the Design and Analysis of Algorithms, By Anany Levitin, 3rd Edition
(Indian), 2017, Pearson.(Chapter 1 (Sections 1.1,1.2), Chapter 2(Sections 2.1,2.2,2.3,2.4),
Chapter 3(Section 3.1,3.2))

Reference Book:
✔ Computer Algorithms/C++, Ellis Horowitz, SatrajSahni and Rajasekaran, 2nd Edition, 2014,
Universities Press.
✔ Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest,
Clifford Stein, 3rd Edition, PHI.
✔ Design and Analysis of Algorithms, S. Sridhar, Oxford (Higher Education)
What is an Algorithm?
An algorithm is a finite set of instructions to solve a particular problem. In addition, all
algorithms must satisfy the following criteria:

✔ Input: Zero or more quantities are externally supplied.

✔ Output: At least one quantity is produced.

✔ Definiteness: Each instruction is clear and unambiguous. It must be perfectly clear what
should be done.

✔ Finiteness: If we trace out the instruction of an algorithm, then for all cases, the
algorithm terminates after a finite number of steps.

✔ Effectiveness: Every instruction must be very basic so that it can be carried out, in
principle, by a person using only pencil and paper. It is not enough that each operation be
definite as in criterion, it also must be feasible.
Algorithm design and analysis process
We now briefly discuss a sequence of steps one typically goes through in designing and
analyzing an algorithm.
Algorithm design and analysis process (Continued)
✔ Understanding the Problem: From a practical perspective, the first thing you need to do
before designing an algorithm is to understand completely the problem given. An input to
an algorithm spec ifies an instance of the problem the algorithm solves. It is very
important to specify exactly the set of instances the algorithm needs to handle.

✔ Ascertaining the Capabilities of the Computational Device: Once you completely

understand a problem, you need to ascertain the capabilities of the computational device
the algorithm is intended for. Select appropriate model from sequential or parallel
programming model.

✔ Choosing between Exact and Approximate Problem Solving: The next principal decision is
to choose between solving the problem exactly and solving it approximately. Because,
there are important problems that simply cannot be solved exactly for most of their
instances and some of the available algorithms for solving a problem exactly can be
unacceptably slow because of the problem’s intrinsic complexity.

✔ Algorithm Design Techniques: 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. They provide guidance for
designing algorithms for new problems, i.e., problems for which there is no known
satisfactory algorithm.
Algorithm design and analysis process (Continued)
✔ Designing an Algorithm and Data Structures: One should pay close attention to choosing
data structures appropriate for the operations performed by the algorithm. For example,
the sieve of Eratosthenes would run longer if we used a linked list instead of an array in its
implementation. Algorithms + Data Structures = Programs

✔ Methods of Specifying an Algorithm: Once you have designed an algorithm; you need to
specify it in some fashion. These are the two options that are most widely used nowadays
for specifying algorithms. Using a natural language has an obvious appeal; however, the
inherent ambiguity of any natural language makes a concise and clear description of
algorithms surprisingly difficult. Pseudocode is a 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.
Algorithm design and analysis process (Continued)
✔ Analyzing an Algorithm: After correctness, by far the most import ant is efficiency. In fact,
there are two kinds of algorithm efficiency: time efficiency, indicating how fast the
algorithm runs, and space efficiency, indicating how much extra memory it uses. Another
desirable characteristic of an algorithm is simplicity. Unlike efficiency, which can be
precisely defined and investigated with mathematical rigor, simplicity, like beauty, is to a
considerable degree in the eye of the beholder.

✔ Coding an Algorithm: Most algorithms are destined to be ultimately implemented as

computer programs. Implementing an algorithm correctly is necessary but not sufficient:
you would not like to diminish your algorithm’s power by an inefficient implementation.
Modern compilers do provide a certain safety net in this regard, especially when they are
used in their code optimization mode.
Analysis Framework
✔ The general framework for analyzing the efficiency of algorithms is discussed
here. There are two kinds of efficiency: time efficiency and space efficiency.
Time efficiency indicates how fast an algorithm in question runs; space efficiency
deals with the extra space the algorithm requires.
✔ In the early days of electronic computing, both resources time and space were at
a premium. Now the amount of extra space required by an algorithm is typically
not of as much concern, In addition, the research experience has shown that for
most problems, we can achieve much more spectacular progress in speed than in
space.
Asymptotic Analysis
✔ The efficiency of an algorithm depends on the amount of time, storage and other
resources required to execute the algorithm. The efficiency is measured with the help of
asymptotic notations.

✔ An algorithm may not have the same performance for different types of inputs. With the
increase in the input size, the performance will change.

✔ The study of change in performance of the algorithm with the change in the order of the
input size is defined as asymptotic analysis.
Asymptotic Notations
✔ Asymptotic notations are the mathematical notations used to describe the running time of
an algorithm when the input tends towards a particular value or a limiting value.

✔ The main idea of asymptotic analysis is to measure the efficiency of the algorithm that
doesn’t depend on machine-specific constants, and doesn’t require algorithms to be
implemented and time taken by program to be compared.

✔ There are mainly three asymptotic notations:

• Big-O notation
• Omega notation
• Theta notation
Big-O Notation (O-notation)
✔ Big-O notation represents the upper bound of the running time of an algorithm. Thus, it
gives the worst-case complexity of an algorithm.

✔ The above expression can be described as a function

f(n) belongs to the set O(g(n)) if there exists a positive
constant c such that it lies between 0 and cg(n), for
sufficiently large n.

✔ For any value of n, the running time of an algorithm

does not cross the time provided by O(g(n)).

✔ Since it gives the worst-case running time of an

algorithm, it is widely used to analyze an algorithm as
we are always interested in the worst-case scenario.
Omega Notation (Ω-notation)
✔ Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.

✔ The above expression can be described as a function

f(n) belongs to the set Ω(g(n)) if there exists a positive
constant c such that it lies above cg(n), for sufficiently
large n.

✔ For any value of n, the minimum time required by the

algorithm is given by Omega Ω(g(n)).
Theta Notation (Θ-notation)
✔ Theta notation encloses the function from above and below. Since it represents the upper
and the lower bound of the running time of an algorithm, it is used for analyzing the
average-case complexity of an algorithm.
✔ For a function g(n), Θ(g(n)) is given by the relation:

✔ The above expression can be described as a function

f(n) belongs to the set Θ(g(n)) if there exist positive
constants c1 and c2 such that it can be sandwiched
between c1g(n) and c2g(n), for sufficiently large n.

✔ If a function f(n) lies anywhere in between c1g(n) and

c2g(n) for all n ≥ n0, then f(n) is said to be
asymptotically tight bound.
Frequency Count Method
Example 1

Algorithm Sum(A,n)
{
s=0;
for(i=0;i<n;i++)
{
s=s+A[i];
}
return s;
}
Frequency Count Method
Example 1

Algorithm Sum(A,n)
{
s=0; 1
for(i=0;i<n;i++) n+1
{
s=s+A[i]; n
}
return s;
1
}

F(n)=2n+3
=O(n)
Frequency Count Method
Example 2

Algorithm Add(A,B,n)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++){
C[i,j]=A[i,j]+B[i,j]
}
}

}
Frequency Count Method
Example 2

Algorithm Add(A,B,n)
{
for(i=0;i<n;i++) n+1
{
for(j=0;j<n;j++){ n*(n+1)
C[i,j]=A[i,j]+B[i,j] n*n
}
}

}
F(n)=2n^2+2n+1
=O(n^2)
Frequency Count Method
Example 3

Algorithm multiply(A,B,n)
{
for(i=0;i<n;i++){
for(j=0;j<n;j++){
C[i,j]=0
for(k=0;k<n;k++){
C[i,j]=C[i,j]+A[i,k]*B[k,i];
}
}
}

}
Frequency Count Method
Example 3

Algorithm multiply(A,B,n)
{
for(i=0;i<n;i++){ n+1
for(j=0;j<n;j++){ n(n+1)
C[i,j]=0 n*n
for(k=0;k<n;k++){ n*n*(n+1)
C[i,j]=C[i,j]+A[i,k]*B[k,i]; n*n*n
}
}
}
F(n)=2n^3 + 3n^2+2n+1
} =O(n^3)
Frequency Count Method
Example 4
P=0;
for(i=1;p<=n;i++)
{
p=p+i;
}
Frequency Count Method
Example 5
for(i=1;i<n;i=i*2)
{
stmt;
}
Frequency Count Method
Example 6
P=0;
for(i=1;i<n;i=i*2)
{
p++;
}
for(j=1;j<p;j=j*2)
{
stmt;
}
Frequency Count Method
Example 6
P=0;
for(i=1;i<n;i=i*2)
{
P=log(n)
p++;
}
for(j=1;j<p;j=j*2)
{
stmt; log(p)
}

=O(log log n)
Recurrence Relation
The analysis of the complexity of a recurrence relation involves finding the asymptotic
upper bound on the running time of a recursive algorithm. This is usually done by finding a
closed-form expression for the number of operations performed by the algorithm as a
function of the input size, and then determining the order of growth of the expression as the
input size becomes large.

Here are the general steps to analyze the complexity of a recurrence relation:
• Substitute the input size into the recurrence relation to obtain a sequence of terms.
• Identify a pattern in the sequence of terms, if any, and simplify the recurrence relation to
obtain a closed-form expression for the number of operations performed by the
algorithm.
• Determine the order of growth of the closed-form expression by using techniques such as
the Master Theorem, or by finding the dominant term and ignoring lower-order terms.
• Use the order of growth to determine the asymptotic upper bound on the running time of
the algorithm, which can be expressed in terms of big O notation.
Recurrence Relation (Example 1)
Void test(int n)
{
if(n>0){
printf(“%d”,n);
test(n-1);
}
Call 4
Call 3
} Call 2
Call 1 Test(0)
Test(1)
Test(2) 1
Test(3) 2
3
Recurrence Relation (Example 1)
Void test(int n)
{
if(n>0){
printf(“%d”,n);
test(n-1);
}

}
Recurrence Relation (Example 1)
Recurrence Relation (Example 2)
Void test(int n)
{
if(n>0){
for(i=0;i<n;i++){
printf(“%d”,n);
}
test(n-1);
}

}
Recurrence Relation (Example 2)
Void test(int n)
{
if(n>0){
for(i=0;i<n;i++){
printf(“%d”,n);
}
test(n-1);
}

}
Recurrence Relation (Example 2)
Recurrence Relation (Example 3)
Void test(int n)
{
if(n>0){
for(i=0;i<n;i=i*2){
printf(“%d”,i);
}
test(n-1);
}

}
Recurrence Relation (Example 4)
Void test(int n)
{
if(n>0){
printf(“%d”,n);
test(n-1);
test(n-1);
}
}
Recurrence Relation (Example 4)
Brute Force Approach
What is the Brute Force Algorithm?
A brute force algorithm is a straight forward approach to solving a problem. It also refers to a
programming style that does not include any shortcuts to improve performance.

• It is based on trial and error where the programmer tries to merely utilize the computer's
fast processing power to solve a problem, rather than applying some advanced algorithms
and techniques developed with human intelligence.
• It might increase both space and time complexity.
• A simple example of applying brute force would be linearly searching for an element in an
array. When each and every element of an array is compared with the data to be searched,
it might be termed as a brute force approach, as it is the most direct and simple way one
could think of searching the given data in the array.
Brute Force Approach
PROS AND CONS OF BRUTE FORCE ALGORITHM:
Pros:
• The brute force approach is a guaranteed way to find the correct solution by listing all the
possible candidate solutions for the problem.
• It is a generic method and not limited to any specific domain of problems.
• The brute force method is ideal for solving small and simpler problems.
• It is known for its simplicity and can serve as a comparison benchmark.
Cons:
• The brute force approach is inefficient. For real-time problems, algorithm analysis often
goes above the O(N!) order of growth.
• This method relies more on compromising the power of a computer system for solving a
problem than on a good algorithm design.
• Brute force algorithms are slow.
• Brute force algorithms are not constructive or creative compared to algorithms that are
constructed using some other design paradigms.
Bubble Sort Algorithm
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent
elements if they are in the wrong order. This algorithm is not suitable for large data sets as its
average and worst-case time complexity are quite high.

• We sort the array using multiple passes. After the first pass, the maximum element goes to
end (its correct position). Same way, after second pass, the second largest element goes to
second last position and so on.

• In every pass, we process only those elements that have already not moved to correct
position. After k passes, the largest k elements must have been moved to the last k
positions.

• In a pass, we consider remaining elements and compare all adjacent and swap if larger
element is before a smaller element. If we keep doing this, we get the largest (among the
remaining elements) at its correct position.
Bubble Sort Algorithm
Bubble Sort Algorithm (Implementation)
Bubble Sort Algorithm (Complexity analysis)
The time complexity of Bubble Sort is O(n^2) in the worst-case scenario and the space
complexity of Bubble sort is O(1). Bubble Sort only needs a constant amount of additional
space during the sorting process.
Best Case Time Complexity Analysis of Bubble Sort: O(N)

The best case occurs when the array is already sorted. So

the number of comparisons required is N-1 and the
number of swaps required = 0. Hence the best case
complexity is O(N).

Worst Case Time Complexity Analysis of Bubble

Sort: O(N2)

The worst-case condition for bubble sort occurs when

elements of the array are arranged in decreasing order.
In the worst case, the total number of iterations or passes
required to sort a given array is (N-1). where ‘N’ is the
number of elements present in the array.
Selection Sort
Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly
selecting the smallest (or largest) element from the unsorted portion and swapping it with
the first unsorted element. This process continues until the entire array is sorted.

1. First we find the smallest element and swap it with the first element. This way we get the
smallest element at its correct position.

2. Then we find the smallest among remaining elements (or second smallest) and swap it
with the second element.

3. We keep doing this until we get all elements moved to correct position.
Selection Sort
Selection Sort
Selection Sort
Selection Sort
Complexity Analysis of Selection Sort
Time Complexity: O(n2) ,as there are two nested loops:
• One loop to select an element of Array one by one = O(n)

• Another loop to compare that element with every other Array element = O(n)

• Therefore overall complexity = O(n) * O(n) = O(n*n) = O(n2)

Auxiliary Space: O(1) as the only extra memory used is for temporary variables.
Selection Sort Implementation
Selection Sort Implementation
Brute Force String Matching Algorithm
1. Start at the beginning of the text and slide the pattern window
over it.
2. At each position of the text, compare the characters in the
pattern with the characters in the text.
3. If a mismatch is found, move the pattern window one position
to the right in the text.
4. Repeat steps 2 and 3 until the pattern window reaches the end
of the text.
5. If a match is found (all characters in the pattern match the
corresponding characters in the text), record the starting
position of the match.
6. Move the pattern window one position to the right in the text
and repeat steps 2-5.
7. Continue this process until the pattern window reaches the end
of the text.
String Matching Algorithm
String Matching Algorithm
String Matching Algorithm (Complexity)
Complexity Analysis of Naive Algorithm:

Best Case: O(n)

•When the pattern is found at the very beginning of the text (or very early on).

•The algorithm will perform a constant number of comparisons, typically on the order
of O(n) comparisons, where n is the length of the pattern.

Worst Case: O(n2)

•When the pattern doesn’t appear in the text at all or appears only at the very end.

•The algorithm will perform O((n-m+1)*m) comparisons, where n is the length of

the text and m is the length of the pattern.

•In the worst case, for each position in the text, the algorithm may need to compare the
entire pattern against the text.
Recurrence Relation (Dividing Functions)
Example 1:
Void test(int n)
{
if(n>1){
printf(“%d”,n);
test(n/2);
}
}
Recurrence Relation (Dividing Functions)
Example 1:
Recurrence Relation (Dividing Functions)
Example 2:
T(n) = 1 n=1
T(n/2) + n n>1
Recurrence Relation (Dividing Functions)
Example 2:
T(n) = 1 n=1
T(n/2) + n n>1
11 Institutions, Infinite Possibilities

We provide 100+ programs across 50 academic streams.