Design and Analysis of Algorithms - 24MCA304

MODULE – 1: Introduction
to Algorithms
Unit I: Introduction to Algorithms:
Introduction, Fundamentals of the Analysis of Algorithm Efficiency,
Brute Force Notion of Algorithm, Fundamentals of Algorithmic Problem
Solving, Important Problem Types, Fundamental data Structures.
Analysis Framework, Asymptotic Notations and Basic efficiency classes,
Mathematical analysis of Recursive and Non-recursive algorithms,
Examples. Selection Sort and Bubble Sort, Sequential Search and String
Matching

24/10/2025 2
 What is an Algorithm?
Algorithm: An algorithm is a finite sequence of unambiguous
instructions to solve a particular problem.

Figure 1. Notion of Algorithm

24/10/2025 3
 Characteristics of a Good Algorithm
• Input
• An algorithm may have zero or more inputs.
• Inputs are the quantities that are externally supplied before or during execution.
• Output
• An algorithm must produce at least one output.
• The output is the result or solution to the given problem.
• Definiteness
• Each step of the algorithm must be clear, precise, and unambiguous.
• There should be no confusion about what action needs to be performed.
• Finiteness
• The algorithm must terminate after a finite number of steps.
• It should not result in an infinite loop.
• Effectiveness
• Every step must be simple, basic, and feasible.
• In principle, it should be possible to perform each step by hand using only paper and pencil.
24/10/2025 4
 Example Euclid’s Algorithm

An algorithm to add two numbers: Problem: Find gcd(m,n), the

1. Start greatest common divisor of two
2. Read two numbers a and b
nonnegative, not both zero integers
m and n Examples: gcd(60,24) = 12,
3. Compute sum =a+b gcd(60,0) = 60, gcd(0,0) = ?
4. Print sum
5. Stop Euclid’s algorithm is based on
repeated application of equality
gcd(m,n) = gcd(n, m mod n) until the
second number becomes 0, which
makes the problem trivial.
24/10/2025 5
 Two descriptions of Euclid’s algorithm

Euclid’s algorithm
Step 1 If n = 0, return m and stop; otherwise go 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 - pseudocode
while n ≠ 0 do
r ← m mod n
m← n
n←r
24/10/2025 6
return m
 Other methods for computing gcd(m,n)
Consecutive integer checking algorithm
Step 1 Assign the value of min{m,n} to t
Step 2 Divide m by t. If the remainder is 0, go to Step 3; otherwise, go
to Step 4
Step 3 Divide n by t. If the remainder is 0, return t and stop; otherwise,
go to Step 4
Step 4 Decrease t by 1 and go to Step 2

Is this slower than Euclid’s algorithm?

How much slower?
24/10/2025 7
Middle-school procedure
Step 1 Find the prime factorization of m
Step 2 Find the prime factorization of n
Step 3 Find all the common prime factors
Step 4 Compute the product of all the common prime factors and
return it as gcd(m,n)
For the numbers 60 and 24
60=[Link]
24=[Link]
Gcd(60,24)= 2.2.3 = 12
Is this an algorithm?
How efficient is it?

24/10/2025 8
 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.

Example: Combination of simple English and C++, the

algorithm

24/10/2025 9
 Analysis Framework
Refers to the structured way we study and evaluate an algorithm’s performance
and resource usage. It provides principles and tools to measure efficiency and
compare algorithms.

I. Measuring an Input’s Size

• The running time of an algorithm usually depends on the size of its input.
• Larger inputs → require more time (e.g., sorting large arrays, multiplying
big matrices).
• To analyze an algorithm’s efficiency, we use a parameter n, which
represents the input size.

24/10/2025 10
Continued…
Choosing the Right Measure of Input Size
• Text-based algorithms (e.g., spell-checking)
• If the algorithm processes characters, input size = number of characters.
• If it processes words, input size = number of words.
• Numerical algorithms (e.g., GCD, factorization)
• For integers, input size is not the value of the number itself, but the number of bits
needed to represent it.
• For a number n, size =

• Example: For n = 13, binary representation is 1101 → 4 bits → input size = 4.

24/10/2025 11
II. Units for Measuring Running time
When we analyze algorithms, we don’t want our efficiency measure to
depend on hardware, programming language, or compiler. Instead, we
look for a more abstract metric.
1. Basic Operation
• Each algorithm has a basic operation → the operation that contributes the
most to the running time.
• Examples:
• Sorting algorithms → Key comparison is the basic operation.
• Matrix multiplication → Multiplications and additions are basic operations.
2. Counting the Basic Operation
• Let cop = execution time of one basic operation on a particular computer.
• Let C(n) = number of times the basic operation is executed for input size n.
• Then, the total running time can be estimated as:

24/10/2025 12
 Input size

T(n) ≈ copC(n)
Running time
Execution time Number of times basic
for basic operation operation is executed

24/10/2025 13
III. Orders of Growth
• It shows how an algorithm’s running time or space usage scales with
large input sizes.
• For large n, the growth rate (e.g., linear, quadratic, exponential)
dominates over constants and smaller terms.

• Choosing an algorithm with a lower order of growth is essential for

handling large problems effectively.
24/10/2025 14
 Performance Analysis

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.

24/10/2025 15
 Space Complexity
• The total amount of memory required by an algorithm to execute
completely.
• Components of Space Complexity:
• Fixed Part (c): Independent of input/output size. Includes memory
for program code, constants, and fixed-size variables.
• Variable Part (Sp): Depends on input size, dynamic memory
allocation, and recursion stack.
• Formula:

where c = fixed memory, Sp = memory based on instance characteristics.

24/10/2025 16
Example : Algorithm abc()
def abc():
a = 10
b = 20
c=a+b
print(c)
• Fixed Component (c): Memory for variables a, b, and c.
• Variable Component (Sp): None (since there is no recursion or input-
dependent memory).
So,

Space complexity = fixed memory (program + constants + variables) +

variable memory (inputs, recursion, dynamic structures).
24/10/2025 17
 Time complexity
• The execution time or run-time of the program is referred to as its time
complexity denoted by

tp (instance characteristics)
• This is the sum of the time taken to execute all instructions in the
program.
• Exact estimation runtime is a complex task, as the number of instructions
executed is dependent on the input data.
• Different instructions will take different time to execute. So for the
estimation of the time complexity we count only the number of program
steps.
24/10/2025 18
 Components of time complexity
Speed of the
computer

Choice of
Programming
Language
Components

Compiler Used

Choice of Algorithm

No(Size) of
inputs/outputs

24/10/2025 19
 Worst case, Best Case and Average case
• Worst case - The efficiency of an algorithm for the input size n for
which the algorithm takes longest time to execute among all possible
input.

• Best Case - The efficiency of an algorithm for the input size n for
which the algorithm takes least time during execution among all
possible input.

• Average case – The average number of basic operations executed will

be considered.
24/10/2025 20
 Asymptotic notations
The efficiency of the algorithm is normally Expressed using Asymptotic
notations. The Order of Growth can be expressed.
• Order of Growth using Asymptotic notations
• Order of Growth using limits

Def: The value of the function may increase or decrease as the value of
n increases. Based on the order of growth of n, the behavior of the
function varies.
Asymptotic notations are the notations using which 2 algorithm can be
compared w.r.t efficiency based on the order of growth of an algorithm’s
basic operation.
24/10/2025 21
 Order of Growth using
Asymptotic notations

O (Big Oh)

Asymptotic Ω(Big Omega)

notations

Θ (Big Theta)

24/10/2025 22
 O (Big Oh)
Big-O notation represents the upper bound of the running time of an algorithm.
If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive constant C and
n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 .

It is a measure of the longest amount of time it could possibly take for the algorithm to complete.

24/10/2025 23
 Ω(Big Omega)
• Omega notation represents the lower bound of the running time of an algorithm.
Thus, it provides the best case complexity of an algorithm.
• The execution time serves as a lower bound on the algorithm's time complexity.
• It is defined as the condition that allows an algorithm to complete statement
execution in the shortest amount of time.

The lower bound implies that below this time the algorithm cannot perform better.

24/10/2025 24
 Θ (Big Theta)
• 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.
• Theta (Average Case) You add the running times for each possible input combination
and take the average in the average case.
• Let g and f be the function from the set of natural numbers to itself. The function f is
said to be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that c1*
g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0

24/10/2025 25
Method – 1:(Step Counting with a Counter Variable)

• A new variable, say count, is added to the program and initialized to 0.

• Each time an instruction (or significant program step) is executed, the
count is incremented.
• When the program finishes, the value of count shows the total
number of steps executed for that input.
• This way, instead of measuring actual execution time, we measure
step counts, which gives a machine-independent estimate of time
complexity.

24/10/2025 26
Example
# Program to add elements of an array
arr = [1, 2, 3, 4, 5]
count = 0 # step counter
sum = 0
count += 1 # for initialization
for i in arr:
count += 1 # loop check
sum += i
count += 1 # addition
count += 1 # loop exit
print("Sum:", sum)
print("Step count:", count)
24/10/2025 27
Method–2 (Tabular / Statement-wise Step Counting)

we don’t run the program. Instead, we analyze it line by line and count
how many times each statement executes in terms of n (input size).

Example Program: Sum of n numbers

sum = 0
for i in range(1, n+1):
sum = sum + i

24/10/2025 28
 Order of Growth using limits
• Instead of using Asymptotic notations, the order of growth can be
obtained by computing the limit of the ratio of the two functions as
shown below.
• If you have a function f(n), its order of growth can be found by
comparing it to another function g(n) using the limit:

24/10/2025 29
Example
Compare the order of growth 1/2n(n-1) and n2 using limits.

24/10/2025 30
Example 2

24/10/2025 31
 Fundamental steps in solving problems

Fig 2. Algorithm Design and Analysis Process

24/10/2025 32
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.
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.
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.
Choosing between Exact and Approximate Problem Solving - The next principal decision is
to choose between solving the problem exactly or solving it approximately. In the former case,
an algorithm is called an exact algo-rithm; in the latter case, an algorithm is called an
approximation algorithm.
Algorithm Design Techniques - Now, with all the components of the algorithmic problem
solving in place, how do you design an algorithm to solve a given problem? This is the main
question this book seeks to answer by teaching you several general 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.
24/10/2025 33
• Designing an Algorithm and Data Structures - While the algorithm design techniques do provide a
powerful set of general ap-proaches to algorithmic problem solving, designing an algorithm for a
particular problem may still be a challenging task. Some design techniques can be simply inapplicable
to the problem in question.
• Methods of Specifying an Algorithm - Once you have designed an algorithm, you need to specify it in
some [Link]’s algorithm is described in words (in a free and also a step-by-step form) and in
pseudocode. These are the two options that are most widely used nowadays for specifying algorithms.
• Proving an Algorithm’s Correctness - Once an algorithm has been specified, you have to prove its
correctness. That is, you have to prove that the algorithm yields a required result for every legitimate
input in a finite amount of time. For example, the correctness of Euclid’s algorithm for computing the
greatest common divisor stems from the correctness of the equality gcd(m, n) = gcd(n, m mod n), the
simple observation that the second integer gets smaller on every iteration of the algorithm, and the fact
that the algorithm stops when the second integer becomes 0.
• Analyzing an Algorithm -We usually want our algorithms to possess several qualities. After
correctness, by far the most important 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.
• Coding an Algorithm -Most algorithms are destined to be ultimately implemented as computer
programs. Programming an algorithm presents both a peril and an opportunity. The peril lies in the
possibility of making the transition from an algorithm to a program either incorrectly or very
24/10/2025 34
inefficiently.
 Sieve of Eratosthenes

24/10/2025 35
 Steps of the Algorithm
1. Create a list of integers from 2 to n.
2. Start with the first prime number p = 2.
3. Repeat steps 3–4 until square root(p) > n.
4. Eliminate all multiples of p (except p itself) from the list.
5. Find the next number in the list greater than p that has not been crossed out; this is the next prime.
6. The remaining numbers in the list are all primes.

List of Primes not exceeding n=20

Example: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Output: 2 3 5 7 11 13 17 19
24/10/2025 36
 Brute Force

A straightforward approach, usually based directly on the problem’s statement and

definitions of the concepts involved .
Characteristics
• Simple and easy to implement.
• Checks every possible candidate solution.
• Usually inefficient for large input sizes.
• Guarantees correctness because it explores all possibilities.
Examples:
1. Computing an (a > 0, n a nonnegative integer)
[Link] n!
3. Multiplying two matrices
[Link] for a key of a given value in a list
24/10/2025 37
 IMPORTANT PROBLEM TYPES
The most important problem types are:
(i). Sorting.
(ii). Searching
(iii). String processing
(iv). Graph problems
(v). Combinatorial problems
(vi). Geometric problems
(vii). Numerical problems.

24/10/2025 38
(i) Sorting
• The sorting problem is to rearrange the items of a given list in nondecreasing (ascending) order.
• Sorting can be done on numbers, characters, strings or records.
• To sort student records in alphabetical order of names or by student number or by student grade-
point average. Such a specially chosen piece of information is called a key.
• An algorithm is said to be in-place if it does not require extra memory, E.g., Quicksort.
• A sorting algorithm is called stable if it preserves the relative order of any two equal elements in
its input.
(ii) Searching
• The searching problem deals with finding a given value, called a search key, in a given set. •
E.g., Ordinary Linear search and fast binary search.
(iii) String processing
• A string is a sequence of characters from an alphabet.
• Strings comprise letters, numbers, and special characters; bit strings, which comprise zeros and
ones; and gene sequences, which can be modeled by strings of characters from the four-
character alphabet {A, C, G, T}. It is very useful in bio informatics.
• Searching for a given word in a text is called string matching

24/10/2025 39
(iv) Graph problems
• A graph is a collection of points called vertices, some of which are connected by line
segments called edges.
• Some of the graph problems are graph traversal, shortest path algorithm, topological
sort, traveling salesman problem and the graph-coloring problem and soon.
(v) Combinational problems
• These are problems that ask, explicitly or implicitly, to find a combinational object
such as a permutation, a combination, or a subset that satisfies certain constraints.
• A desired combinatorial object may also be required to have some additional
property such s is a maximum value or a minimum cost.
• In practical, the combinatorial problems are the most difficult problems in
computing.
• Thetravelingsalesmanproblemandthegraphcoloringproblemareexamplesof
combinatorial problems.

24/10/2025 40
(vi) Geometric problems
• Geometric algorithms deal with geometric objects such as points, lines, and
polygons.
• Geometric algorithms are used in computer graphics, robotics, and
tomography.
• The closest-pair problem and the convex-hull problem are comes under this
category.
(vii) Numerical problems
• Numerical problems are problems that involve mathematical equations,
systems of equations, computing definite integrals, evaluating functions, and
soon.
• The majority of such mathematical problems can be solved only
approximately.
24/10/2025 41
 Useful Property Involving the Asymptotic
Notations
The following property, in particular, is useful in analyzing algorithms that
comprise two consecutively executed parts.

THEOREM If f1(n) ∈ O(g1(n)) and f2(n) ∈ O(g2(n)), then

f1(n) + f2(n) ∈ O(max{g1(n), g2(n)}).

If an algorithm has two consecutive parts with complexities and , the overall
complexity is dominated by the "slower-growing" (maximum) one.
When you add two functions, the faster-growing one dominates
asymptotically.
Example: .
Here, grows faster than , so the overall complexity is .

Let t1(n)= =16

Let t2(n)=n log n=4×2=8
So,𝑡1(4)+𝑡2(4)=16+8=24
Asymptotically:𝑂(max⁡{,𝑛log⁡𝑛})=𝑂().
Even though 𝑛log⁡𝑛 contributed 8 here, dominates for large n.
• So what does this property imply for an algorithm that comprises two
consecutively executed parts?
• It implies that the algorithm’s overall efficiency is determined by the
part with a higher order of growth, i.e., its least efficient part:
 Basic Efficiency Classes
• Algorithm efficiency follows among different efficiency classes.
 Efficiency Classes for n = 4

Efficiency Class Growth Rate Operations (n=4) Example Algorithm

Constant 1 Array access
Logarithmic 2 Binary search
Linear 4 Linear search
Linearithmic 4×2=8 Merge sort
Quadratic 16 Bubble sort
Naïve matrix
Cubic 64
multiplication

Recursive subset
Exponential 16
generation

Traveling Salesman (brute

Factorial 24
force)
 Properties of Asymptotic Notations
1. General Properties
• If f(n) is O(g(n)) then a*f(n) is also O(g(n)), where a is a constant.
• Example
f(n) = 2n²+5 is O(n²)
then, 7*f(n) = 7(2n²+5) = 14n²+35 is also O(n²).

• Similarly, this property satisfies both Θ and Ω notation. We can say,

• If f(n) is Θ(g(n)) then a*f(n) is also Θ(g(n)), where a is a constant.
• If f(n) is Ω (g(n)) then a*f(n) is also Ω (g(n)), where a is a constant.
 Mathematical analysis of Non-recursive algorithms

General Plan for Analysing the Time Efficiency of Non recursive Algorithms
• Decide on a parameter (or parameters) indicating an input’s size.
• Identify the algorithm’s basic operation. (As a rule, it is located in the inner-
most loop.)
• Check whether the number of times the basic operation is executed depends
only on the size of an input. If it also depends on some additional property,
the worst-case, average-case, and, if necessary, best-case efficiencies have
to be investigated separately.
• Obtain the total number of times a basic operation is executed.
• Simplify using standard formulas and obtain the order of growth.
EXAMPLE Consider the problem of finding the value of the largest
element in a list of n numbers.

ALGORITHM : MaxElement(A[0..n − 1])

//Determines the value of the largest element in a given array
//Input: An array A[0..n − 1] of real numbers
//Output: The value of the largest element
A maxval ← A[0]
for i ← 1 to n − 1 do
if A[i] > maxval
maxval ← A[i]
return maxval
A = 3 8 5 1 4 n=5

Maxval = 3
 Mathematical analysis of Recursive
algorithms

General Plan for Analysing the Time Efficiency of Recursive Algorithms

• Decide on a parameter (or parameters) indicating an input’s size.

• Identify the algorithm’s basic operation.
• Check whether the number of times the basic operation is executed can vary on different
inputs of the same size; if it can, the worst-case, average-case, and best-case efficiencies
must be investigated separately.
• Set up a recurrence relation, with an appropriate initial condition, for the number of
times the basic operation is executed.
• Solve the recurrence or, at least, ascertain the order of growth of its solution.
EXAMPLE : Compute the factorial function F (n) = n! for an arbitrary non negative
integer n. Since

n! = 1 . . . (n − 1) n = (n − 1)! n
. . . .
for n ≥ 1

and 0! = 1 by definition, we can compute F (n) = F (n − 1) . n with the following

recursive algorithm.

ALGORITHM: F(n)
//Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n!
if n = =0 return 1
else return F (n − 1) ∗ n
• Example : Program to find 5!.
• F(5)=5*fact(4)

• Basic operation here is multiplication.

• Number of executions we denote M(n).

• M(n) = M(n-1)+1 ---> recurrence relations or recurrences

Problems
1. Solve the following recurrence relations.
a. x(n) = x(n − 1) + 5 for n > 1, x(1) = 0

Step 1: Expand the recurrence

• base case)

• So sequence looks like:

• Step 2: Find the pattern

• Clearly, is increasing by 5 each time.
So it’s an arithmetic sequence.
• General formula for arithmetic progression:

where .
b. x(n) = 3x(n − 1) for n > 1, x(1) = 4
Sorting Techniques
Sorting - Introduction
Sorting refers to the arranging a set of data elements in some logical order. The
logical order refers to ascending or descending order of data values.

For ex. A telephone directory can be considered as a list where each record has
three fields - name, address and phone number.
The details are listed in the directory based on the names in alphabetical order.
These records can arrange in any way like by phone number or name. This
arrangement of records is known as sorting.
Sorting - Introduction
Sorting is among the most basic problems in algorithm design.
We are given a sequence of items, each associated with a given key value. And the
problem is to rearrange the items so that they are in an increasing(or decreasing)
order by key.
The methods of sorting can be divided into two categories:
Internal Sorting
External Sorting
Sorting - Introduction
Internal Sorting
If all the data that is to be sorted can be adjusted at a time in main memory,
then internal sorting methods are used
External Sorting
When the data to be sorted can’t be accommodated in the memory at the same
time and some has to be kept in auxiliary memory, then external sorting methods
are used.
NOTE: We will only consider internal sorting
Efficiency of Sorting
The complexity of a sorting algorithm measures the running time of a function in
which n number of items are to be sorted.
The choice of sorting method depends on efficiency considerations for different
problems.
The most important of these considerations are:
 The length of time spent by programmer in coding a particular sorting program

 Amount of machine time necessary for running the program

 The amount of memory necessary for running the program

Efficiency of Sorting
Various sorting methods are analyzed in the cases like – best case, worst case or
average case.
Most of the sort methods we consider have requirements that range from
0(nlogn) to 0(n2).
A sort should not be selected only because its sorting time is 0(nlogn); the
relation of the file size n and the other factors affecting the actual sorting time
must be considered.
Determining the time requirement of sorting technique is to actually run the
program and measure its efficiency.
Efficiency of Sorting
Once a particular sorting technique is selected the need is to make the program
as efficient as possible.
Any improvement in sorting time significantly affect the overall efficiency and
saves a great deal of computer time.
Space constraints are usually less important than time considerations.

The reason for this can be, as for most sorting programs, the amount of space
needed is closer to 0(n) than to 0(n2).
The second reason is that, if more space is required, it can almost always be
found in auxiliary storage.
Efficiency of Sorting
An ideal sort is an in-place sort where the algorithm uses no additional array
storage, and hence it is possible to sort very large lists without the need to
allocate additional working storage.
A sorting algorithm is said to be stable if two objects with equal keys appear in
the same order in sorted output as they appear in the input unsorted array.
Some sorting algorithms are stable by nature like Insertion sort, Merge Sort,
Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort,
etc.
Types of Sorting
Bubble Sort

Selection Sort

Insertion Sort

Merge Sort

Quick Sort

Heap Sort
Selection Sort
Find the least( or greatest) value in the array, swap it into the leftmost(or
rightmost) component, and then forget the leftmost component, Do this
repeatedly.
Let a[n] be a linear array of n elements. The selection sort works as follows:
We start selection sort by scanning the entire given list to find its smallest element
and exchange it with the first element, putting the smallest element in its final
position in the sorted list.
Then we scan the list, starting with the second element, to find the smallest among
the last n − 1 elements and exchange it with the second element, putting the
second smallest element in its final position.
Generally, on the ith pass through the list, which we number from 0 to n − 2, the
algorithm searches for the smallest item among the last n − i elements and swaps it
with Ai.
After n − 1 passes, the list is sorted.
The smallest element from ith position onwards can be obtained using
the following code.
pos  i where i =0,1,2,3
for j  i+1 to n-1
if (a[j]<a[pos]) posj
end for
After finding the position of the smallest number , it should be
exchange with ith position.
temp a[pos]
a[pos]a[i]
a[i]temp
pseudocode of algorithm
ALGORITHM SelectionSort(A[],n)
//Sorts a given array by selection sort
//Input: An array A[0..n − 1] of orderable elements
//Output: Array A[0..n − 1] sorted in nondecreasing order

for i ← 0 to n − 2 do
min ← i
for j ← i + 1 to n − 1 do
if A[j ] < A[min] min ← j swap A[i] and A[min]
Selection Sort
F
Selection Sort
Selection Sort
Selection Sort
Selection Sort
 Selection Sort
Analysis
• Step 1: The parameter to be considered is n, which represents the size of the
input.
• Step 2: The basic operation is the comparative statement if a[j]<a[pos] in the
innermost for loop.
• Step 3: The number of comparisons depends on the value of n and the
number of times the two for loops are executed.
for j 1 to n-1 do
for i 0 to n-j-1 do
if (a[i]>a[i+1])

n 1 n j  1
  1
f(n) = j 1 i 0

 (n 2 )
 Selection Sort
Procedure for Selection Sort
 Selection Sort
Time Complexity
• Inner loop executes (n-1) times when i=0, (n-2) times when i=1 and so on:
• Time complexity = (n-1) + (n-2) + (n-3) + …....... +2+1 = O(n2)

Space Complexity
• Since no extra space beside n variables is needed for sorting so
• O(n)
 Selection Sort
Advantages and Disadvantages
Advantages
Very simple and easy to understand
Easy to implement the algorithm correctly and hence function can be
written easily.
Straight forward approach
Disadvantages
Time complexity is not efficient. Many other sorting techniques
presents time efficiency N log N.
Even if the elements are sorted , n-1 passes are required.
 Bubble Sort
• In bubble sort, each element is compared with its adjacent element.

• We begin with the 0th element and compare it with the 1st element.

• If it is found to be greater than the 1st element, then they are interchanged.

• In this way all the elements are compared (excluding last) with their next element
and are interchanged if required

• On completing the first iteration, largest element gets placed at the last position.
Similarly in second iteration second largest element gets placed at the second last
position and so on.
 Bubble Sort

for j =1 to n-1
for i=0 to n-j-1
if (a[i]<a[i+1])
exchange (a[i],a[i+1])
end if
end for
end for
 Bubble Sort

pseudocode of algorithm

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

//Sorts a given array by bubble sort
//Input: An array A[0..n − 1] of orderable elements
//Output: Array
A[0..n − 1] sorted in nondecreasing order for i ← 0 to n − 2 do
for j ← 0 to n − 2 − i do
if A[j + 1] < A[j ] swap A[j ] and A[j + 1]
 Bubble Sort
Advantages and Disadvantages
Advantages
Very simple and easy to program.
Straight forward approach .
Disadvantages
It runs slowly hence it is not efficient. More efficient algorithms are
present.
Even if the elements are sorted , n-1 passes are required.
Bubble Sort
Pass-01
Bubble Sort
Pass-02
Bubble Sort
Pass-03
Bubble Sort
Bubble Sort
Works best when array is already nearly sorted worst case number of comparisons
is O(n2)
– e.g. input array values are 10,9,8,7,6,5,4,3,2,1
– On each step comparison required 9+8+7+... +1
– (n-1)*n /2
– O(n2)

Best case occurs when the array is already sorted and its complexity is O (n)
– input is in order (1,2,3,4,5,6,7,8,9,10)
– the algorithm still goes over each element once and checks if a swap is necessary.
 Searching
Searching Technique used to find the location of the target data item among the
list of objects.
Searching is to find the location of the given target element.
Searching Algorithm:
1. Sequential Search – Used when the list is unordered.
2. Binary Search - Used when the list is ordered.

3 4 5 9 1
 Sequential Search

• The Sequential Search , also called Linear search.

• To repeat, the algorithm simply compares successive elements of a
given list with a given search key until either a match is encountered
(successful search) or the list is exhausted without finding a match
(unsuccessful search).
• A simple extra trick is often employed in implementing sequential
search: if we append the search key to the end of the list, the search
for the key will have to be successful, and therefore we can eliminate
the end of list check altogether.
 Sequential Search
ALGORITHM SequentialSearch2(A[0..n], K)
//Implements sequential search with a search key as a sentinel
//Input: An array A of n elements and a search key K
//Output: The index of the first element in A[0..n − 1] whose value is
equal to K or −1 if no such element is found
A[n] ← K i ← 0
while A[i] = K do i ← i + 1
if i < n return i else return −1
 String Matching
• String Matching is the process of finding the occurrence(s) of a
smaller string (called the pattern) within a larger string (called the
text).
• Example:
text F U N - U N C L E
pattern U N C L E

• Given a string called pattern with m character and other string called
text with n character where m<=n.

24/10/2025 89
 i
0 1 2 3 4 5 6 7 8
text F U N - U N C L E
pattern U N C L E
0 1 2 3
j
i
0 1 2 3 4 5 6 7 8
text F U N - U N C L E
pattern U N C L E
j

24/10/2025 90
Algorithm String_Match(pattern,text)
nlength (text)
mlength(pattern)
for i o to n-m do
j0
while j<m and pattern[j]=text[i+j]
jj+1
end while
If j=m return i
end for
return -1

24/10/2025 91
 for i 0 to n-m do
for j 0 to m-1 do
if (pattern[j]=text[i+j])

𝑛− 𝑚 𝑚−1

f(n) = ∑ ∑1
𝑖=0 𝑗=0

Time complexity of string matching f(n)= O(mn)

24/10/2025 92
Divide and Conquer
Divide-and-conquer technique breaks a problem into sub problems that are similar to the original problem,
recursively solves the sub problems and finally combines the solutions of the sub problems to solve the original
problem.
Think of a divide-and-conquer algorithm as having three parts:
• Divide the problem into a number of subproblems that are smaller instances of the same problem.
• Conquer the sub problems by solving them recursively. If they are small enough, solve the subproblems as base
cases.
• Combine the solutions of the sub problems to achieve the solution for the original problem.
Merge Sort
• Merge sort is a sorting technique designed based on Divide and Conquer technique.
• Merge sort first divides the array into equal halves recursively and then combine (merge) them
in sorted order into a single array.
• With worst-case time complexity being Ο(n log n), it is one of the most respected algorithms.
• Because we're using divide-and-conquer technique to sort, we need to decide what our sub
problems are going to be.
Full Problem: Sort an array of n elements.
Sub Problem: Split into smaller sub-arrays recursively and sort them individually.
Merging all these sub-arrays in recursive order to form a single array.
• Let a[n]is an array of n elements, we say the original problem is to sort array[0….n-1].
Merge Sort
1. Divide the array into two halves by finding the mid position such that mid should be between
lower bound (low)and upper bound (high).
2. Conquer by recursively sorting the subarrays in each of the two sub problems created by the
divide step. That is, recursively sort the subarray a[low.….mid] and recursively sort the
subarray a[mid+1….high].
3. Combine (Merge)by merging the two sorted sub arrays back into the single sorted subarray
a[low….high].
Merge Sort
mid 0 1 2 3 4 5 6 7 8
15 5 24 8 1 3 16 12 21
mid

0 1 2 3 4 5 6 7 8 mid
mid 15 5 24 8 1 3 16 12 21

0 1 2 3 4 5 6 7 8
15 5 24 8 1 3 16 12 21
m

0 1 2 3 4 5 6 7 8
15 5 24 8 1 3 16 12 21

0 1
15 5
Merge Sort
0 1 2 3 4
8 1 5 6 7 8
15 5 24
3 16 12 21

0 1 3 4
15 5 1 8 5 6 7 8
3 16 12 21
0 1
5 15
0 1 2
5 15 24

0 1 2 3 4 5 6 7 8
1 5 8 15 24 3 12 16 21

0 1 2 3 4 5 6 7 8
Final Sorted Array =>
1 3 5 8 12 15 16 21 24
Merge Sort Code
merge_sort(int a[],int low, int high){
If(low < high)
{
mid=(low+high)/2;
merge_sort(a,low,mid);
merge_sort([Link]+1,high);
merge(a,low,mid,high);
}
}
Merge Sort Code
// Merge two subarrays L (Left array) and R (Right array) into arr
void merge(int arr[], int left, int mid, int right) {
int len1 = mid - left + 1;
int len2 = right - mid;
int L[len1], R[len2];
for (int i = 0; i < len1; i++)
L[i] = arr[left + i];

for (int j = 0; j < len2; j++)

R[j] = arr[mid + 1 + j];
// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = left; // Until we reach either end of either L or R, pick larger elements, among L and R and place
them in the correct position at A[p..r]
while (i < len1 && j < len2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < len1) // When we run out of elements in either L or R, pick up the remaining elements and put in A[p..r]
arr[k++] = L[i++];
while (j < len2)
arr[k++] = R[j++];
}
Analysis of Merge Sort
The time to merge sort n numbers is equal to the time to do two recursive
merge sorts of size n/2 plus the time to merge, which is linear.
We can express the number of operations involved using the following
recurrence relations
T(1)=1
T(n) =2T(n/2)+n
Going further down using the same logic
T(n/2)=2T(n/2)+n/2
Continuing in this manner, we can write
T(n)=nT(1)+nlogn
=n+nlogn
T(n)=O(nlogn)
Quick Sort
Quick sort is yet another sorting algorithm designed based on Divide and Conquer technique.
This is one of the best efficient algorithm known for the partitioning the given array based on
pivot element.

Since it uses the partition technique to divide the given array into two sub arrays and apply the
same procedure to each of them recursively till elements get sorted.
It is known as Partition Exchange Sorting technique.

Partitioning can be done by picking the pivot element from the given array.
The pivot element can be picked in many ways by different programmers.
1. Choose first element as pivot element.
2. Choose last element as pivot element.
3. Choose middle element or any random element as pivot element.
Merge Sort Code
// Merge two subarrays L (Left array) and R (Right array) into arr
void merge(int arr[], int left, int mid, int right) {
int len1 = mid - left + 1;
int len2 = right - mid;
int L[len1], R[len2];
for (int i = 0; i < len1; i++)
L[i] = arr[left + i];

for (int j = 0; j < len2; j++)

R[j] = arr[mid + 1 + j];
// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = left; // Until we reach either end of either L or R, pick larger elements, among L and R and place
them in the correct position at A[p..r]
while (i < len1 && j < len2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < len1) // When we run out of elements in either L or R, pick up the remaining elements and put in A[p..r]
arr[k++] = L[i++];
while (j < len2)
arr[k++] = R[j++];
}
Analysis of Merge Sort
The time to merge sort n numbers is equal to the time to do two recursive
merge sorts of size n/2 plus the time to merge, which is linear.
We can express the number of operations involved using the following
recurrence relations
T(1)=1
T(n) =2T(n/2)+n
Going further down using the same logic
T(n/2)=2T(n/2)+n/2
Continuing in this manner, we can write
T(n)=nT(1)+nlogn
=n+nlogn
T(n)=O(nlogn)
Quick Sort
Quick sort is yet another sorting algorithm designed based on Divide and Conquer technique.
This is one of the best efficient algorithm known for the partitioning the given array based on
pivot element.

Since it uses the partition technique to divide the given array into two sub arrays and apply the
same procedure to each of them recursively till elements get sorted.
It is known as Partition Exchange Sorting technique.

Partitioning can be done by picking the pivot element from the given array.
The pivot element can be picked in many ways by different programmers.
1. Choose first element as pivot element.
2. Choose last element as pivot element.
3. Choose middle element or any random element as pivot element.