1

Dr. H N National College of Engineering

Department of Artificial Intelligence and Data Science
Analysis & Design of Algorithms
Module-1
By,
Dr. Vikhyath K B

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Introduction
2

Why do you need to study algorithms ?

¨ From a practical standpoint, you have to know a standard set of important

algorithms from different areas of computing; in addition, you should be able to
design new algorithms and analyze their efficiency.

¨ From the theoretical stand point, the study of algorithms, sometimes called
algorithmics, has come to be recognized as the cornerstone of computer science.

Algorithmics: the Spirit of Computing, put it as follows:

¨ Algorithmics is more than a branch of computer science. It is the core of computer

science, and, in all fairness, can be said to be relevant to most of science, business,
and technology.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Design
3

¨ Design is the process of creating a step-by-step logical solution (algorithm) to

solve a given problem efficiently.

Linear Search: Linear Search checks each element one by one until the target element
is found or the list ends.

Example: Search for 25 in the array:

A = [10, 5, 18, 25, 30]

Binary Search: Binary Search works on a sorted array and repeatedly divides the
search space into half.

Example: Search for 25 in the sorted array:

A = [5, 10, 18, 25, 30]
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
4

Step-by-Step Process:

¨ Middle element = 18
¨ 25 > 18 → Search right half
¨ New middle = 25
¨ 25 == 25 ✅ (Found)

Linear search works on the principal of Brute-Force and the binary search works on
the principle of Divide-Conquer technique.

¨ The course primarily focuses on various design techniques used to solve specific
problems.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Different algorithm design techniques
5

¨ Brute Force Technique

¨ Divide and Conquer

¨ Decrease and Conquer

¨ Transform and Conquer

¨ Greedy Method

¨ Dynamic Programming

¨ Backtracking

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Analysis and Design of Algorithms (ADA)
6

Analysis : is the process of evaluating an algorithm to determine its efficiency in

terms of time and space requirements.

After designing an algorithm, we analyze:

¨ Time Complexity → How much time the algorithm takes to run

¨ Space Complexity → How much memory it uses
¨ Best, Average, and Worst Case performance.

Generally:

Design → Creating the algorithm

Analysis → Measuring how efficient the algorithm is.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 What Is an Algorithm?
7

¨ Is a method to solve a problem.

¨ Is a sequence of computational steps that transforms input into output.

¨ An algorithm is a sequence of unambiguous instructions for solving a problem.

The notion of the algorithm

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
 The standard properties (characteristics) of
an algorithm
8

¨ Input: An algorithm must have zero or more inputs.

¨ Output: An algorithm must produce at least one output.

¨ Definiteness (Unambiguity): Each step must be clear and precisely defined.

¨ Finiteness: An algorithm must terminate after a finite number of steps.

¨ Effectiveness (Feasibility): Each step must be basic and executable in finite time.

¨ Correctness (Additional Property): Algorithm should produce the correct

output for all valid inputs.

¨ Generality (Additional Property): Algorithm should work for all inputs of the
problem type, not just a specific case.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Examples illustrating the idea of the
algorithm:
9

Here we considered three methods for solving the same problem: computing the greatest
common divisor (GCD) of two integers.

These examples will help us to illustrate several important points:

¨ The non-ambiguity requirement for each step of an algorithm cannot be compromised.

¨ The range of inputs for which an algorithm works has to be specified carefully.

¨ The same algorithm can be represented in several different ways.

¨ There may exist several algorithms for solving the same problem.

¨ Algorithms for the same problem can be based on very different ideas and can solve the
problem with dramatically different speeds.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 1. Euclid’s Algorithm
10

Input: Two positive numbers a and b

Output: Largest integer which divides a and b

Step1: If b = 0, return the value of a as the answer and stop; otherwise, proceed to Step 2.

Step2: Divide a by b and assign the value of the remainder to r.

Step3: Exchange the value of a by b and b by r. Go to Step1.

a b r
Example: Apply Euclid’s Algorithm for the 6 10 6
value a=6 and b=10. 10 6 4
6 4 2
¨ Therefore GCD (6, 10) =2 4 2 0
2 0 Stop as b=0
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
 Pseudocode
11

Pseudocode is an informal, simple, and structured way of writing an algorithm using

plain language mixed with programming like statements, without following the strict
syntax of any programming language.

ALGORITHM Euclid(a, b)

//Computes gcd(a, b) by Euclid’s algorithm

//Input: Two nonnegative, not-both-zero integers a and b
//Output: Greatest common divisor of a and b

while b =
̸ 0 do
¨ r ←a mod b
¨ a←b
¨ b←r
¨ return a
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
 2. Consecutive integer checking
12
method
Input: a and b values
¨
GCD(a,b)<=min(a,b)
¨ Output: GCD of a and b
¨ Step 1: Assign the value of min{a, b} to t.
¨ Step 2: Divide a by t. If the remainder of this division is 0, go to Step 3; otherwise, go
to Step 4.
¨ Step 3: Divide b 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. t a mod t b mod t
¨ Step 4: Decrease the value of t by 1. Go to Step 2. 6 0 4
5 1 -
Example: Apply consecutive integer check method
4 2 -
To find the GCD, where a=6 and b=10.
3 0 1
¨ Therefore GCD (6, 10) = 2 2 0 0
Drawback: If either a or b is zero, the algorithm will not work.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
 3. Middle school method
13

¨ Input: a and b values

¨ Output: GCD of a and b
¨ Step1: Find prime factors of a
¨ Step2: Find prime factors of b
¨ Step3: The product of the common factors is the GCD

Example: Apply Middle school method, to find the GCD, where a=6 and b=10.

Step 1: Prime Factorization

¨ 6=2×3
¨ 10=2×5

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

14

Step 2: Identify Common Prime Factors

¨ Common prime factor between 6 and 10: 2

Step 3: Multiply Common Factors

¨ GCD=2

¨ Therefore GCD(6, 10) = 2

Drawbacks:

¨ The method does not clearly explain how to determine the prime factors in Step 1
and Step 2, resulting in ambiguity. Therefore, it fails to satisfy the requirement of
definiteness (or effectiveness).
¨ The method fails when either value a or b equals 1, since 1 is not a prime number.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Fundamentals of Algorithmic
15
Problem Solving.
¨ An algorithm is a procedural solutions for solving a problem. These solutions are
not answers but specific instructions for getting answers.

Sequence of steps in designing and analysing an algorithm.

Understanding the Problem:

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

¨ Many computing problems are recurring types, and known algorithms can often be
used to solve them.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
16

¨ Understanding an algorithm’s working, strengths, and weaknesses is important

when selecting the most suitable one.

¨ When no ready-made algorithm exists, you must design your own using a
systematic sequence of steps.

¨ An input to an algorithm represents a specific instance of the problem it is designed

to solve.

¨ It is essential to clearly define the complete set of valid input instances the
algorithm must handle.

¨ A correct algorithm must work for all legitimate inputs, including boundary cases
not just for most inputs.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
17

Process of Algorithm & Design

18

Ascertaining the Capabilities of the Computational Device:

¨ Most algorithms are designed for the sequential RAM model, based on the John
von Neumann architecture, where instructions execute one at a time.

¨ Modern computers can perform operations concurrently, leading to parallel

algorithms, but the RAM model remains fundamental in algorithm design and
analysis.

¨ Concern about speed and memory depends on context: it is usually ignored in

theoretical design, but crucial for complex, large-scale, or time-critical practical
problems.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

19

Choosing between Exact and Approximate Problem Solving:

¨ A key decision in algorithm design is choosing between an exact algorithm

(precise solution) and an approximation algorithm (near-optimal solution).

¨ Approximation algorithms are used when exact solutions are impossible for most
instances (e.g., square roots, nonlinear equations, definite integrals) or when exact
algorithms are too slow due to high complexity.

¨ Approximation algorithms can also serve as components within more advanced

algorithms that ultimately produce exact solutions.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

20

Algorithm Design Techniques:

¨ An algorithm design technique (strategy/paradigm) is a general problem-

solving approach applicable to many different computing problems.

¨ These techniques guide the creation of algorithms for new problems where no
known satisfactory solution exists.

¨ Algorithm design techniques help classify and study algorithms based on their
underlying design ideas, forming a foundation of computer science.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

21

Designing an Algorithm and Data Structures:

¨ Even with general algorithm design techniques, creating an algorithm for a specific
problem can be difficult; some techniques may not apply, and multiple techniques
may need to be combined.

¨ Selecting appropriate data structures is crucial, as they significantly affect an

algorithm’s efficiency and performance.

¨ Some design techniques rely heavily on structuring or restructuring data,

highlighting the strong relationship between algorithms and data structures.

¨ The principle “Algorithms + Data Structures = Programs” emphasizes their

fundamental importance in programming.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

22

Methods of Specifying an Algorithm:

¨ Algorithms are commonly specified using natural language or pseudocode, with

pseudocode being more precise and concise.

¨ Natural language descriptions can be ambiguous, whereas pseudocode combines

programming constructs with plain language for clarity.

¨ Flowcharts were once widely used but are now largely outdated for complex
algorithms.

¨ An algorithm description must be converted into a program in a specific

programming language for execution; the program represents the algorithm’s
implementation.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

23

Proving an Algorithm’s Correctness:

¨ After specification, an algorithm’s correctness must be proven, meaning it

produces the required result for every legitimate input in a finite amount of time.

¨ Mathematical induction is a common technique for proving correctness, while

testing with specific inputs cannot conclusively prove correctness.

¨ For approximation algorithms, correctness involves proving that the error stays
within a predefined acceptable bound.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

24

Analysing an Algorithm:

¨ After correctness, efficiency is the most important quality of an algorithm,

measured in terms of time efficiency (running time) and space efficiency (memory
usage).

¨ Simplicity is desirable because simpler algorithms are easier to understand,

implement, and debug, though sometimes a trade-off between simplicity and
efficiency is necessary.

¨ Generality is important: an algorithm should solve a suitably general problem and

handle a natural set of inputs, but unnecessary over-generalization should be
avoided.

¨ Algorithm design is often iterative; if efficiency, simplicity, or generality is

unsatisfactory, the algorithm should be refined or redesigned.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
25

Coding an Algorithm:

¨ Correct program implementation is crucial; while formal verification methods

exist. In practice correctness is mainly ensured through testing and debugging.

¨ Efficient implementation matters: code optimization techniques can improve

performance by constant factors, but choosing a better algorithm yields far greater
improvements.

¨ Algorithm design is iterative and involves trade-offs among efficiency, simplicity,

and available resources; perfection is not always practical.

¨ Not all problems are solvable by algorithms. some are undecidable, though most
practical computing problems are algorithmically solvable.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Fundamentals of the Analysis of
26
Algorithm Efficiency
¨ Analysis of algorithms mainly refers to studying an algorithm’s efficiency,
specifically in terms of running time and memory space.

¨ Asymptotic notations — Big O (“big oh”) , Big Ω (“big omega”), and Big Θ (“big
theta”) — as the standard mathematical language for expressing algorithm
efficiency.

¨ Non-recursive algorithms are analysed using summations, while recursive

algorithms are analysed using recurrence relations. A recurrence defines the
running time in terms of smaller input sizes.

¨ Besides mathematical analysis, empirical analysis and algorithm visualization

are complementary approaches for studying algorithm efficiency.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

27

Empirical Analysis

¨ Involves implementing the algorithm and running it on different inputs.

¨ The program’s actual running time is measured.
¨ The results are analysed to observe performance trends.
¨ It gives practical performance data, but results may vary depending on hardware,
compiler, and input type.

Algorithm Visualization

¨ Uses graphical tools or animations to visually demonstrate how an algorithm

works.
¨ Helps understand how operations grow as input size increases.
¨ Useful for spotting inefficiencies or performance patterns.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
 The Analysis Framework
28

¨ Algorithm efficiency is measured in two ways: time efficiency (time complexity)

and space efficiency (space complexity).

¨ Time complexity measures how fast an algorithm runs, while space complexity
measures the extra memory used beyond input and output storage.

¨ Although advances in technology have greatly increased memory capacity, time

efficiency remains the primary concern in algorithm analysis.

¨ The general framework for analysis mainly focuses on time efficiency but can also
be applied to space efficiency.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

29

Measuring an Input’s Size:

¨ Algorithm efficiency is analysed as a function of input size (n), since most

algorithms take longer to run on larger inputs.

¨ The choice of input size parameter depends on the problem (e.g., list size for
sorting, degree or number of coefficients for polynomials).

¨ For numerical problems (e.g., primality testing), input size is best measured by the
number of bits in the number’s binary representation, not by its magnitude.

b = ⌊log2 n⌋ + 1.
¨ means:
• b = number of bits required to represent the number n
• log₂ n = logarithm of n base 2
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
30

• ⌊ ⌋ (floor) = take the greatest integer less than or equal to the value
• +1 accounts for the leading bit

Example
q Let n = 10
q Compute log₂(10) ≈ 3.32
q Floor value → 3
q Add 1 → b = 4
q Binary of 10 = 1010, which indeed uses 4 bits.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

31

Units for Measuring Running Time:

¨ Measuring an algorithm’s running time in seconds is unreliable because it depends

on the computer, program, and compiler; instead, efficiency is measured by
counting the executions of the algorithm’s basic operation.

¨ The basic operation is the most time-consuming operation, usually in the

innermost loop (e.g., key comparisons in sorting, division in arithmetic algorithms
is slowest, then multiplication, then addition/subtraction).

¨ The running time of an algorithm can be estimated as: T(n)≈cop×C(n)

¨ Where cop is the time per basic operation and C(n) is the number of times it is
executed.
¨ In efficiency analysis, multiplicative constants are ignored, focusing on the
order of growth of the basic operation count for large inputs.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
32

Orders of Growth:

¨ For large input sizes, the order of growth of a function is more important than
exact running time differences on small inputs, because efficiency differences
become significant only for large n.

¨ Logarithmic functions (log n) grow very slowly and are extremely efficient; the
base of the logarithm does not affect its growth order since changing bases only
changes a constant factor.

¨ Exponential (2ⁿ) and factorial (n!) functions grow extremely fast, making
algorithms with such time complexities practical only for very small input sizes.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

33

¨ Different growth rates respond very differently to doubling input size:

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

34

¨ log n increases slightly,

¨ n doubles,
¨ n² quadruples,
¨ n³ increases eightfold,
¨ 2ⁿ squares,
¨ n! grows dramatically.

¨ Therefore, algorithms with polynomial or logarithmic growth are generally

feasible, while exponential-growth algorithms quickly become impractical for large
inputs.

¨ Algorithms have different growth rates (like O(n), O(n2) O(logn), etc.).
When the input size doubles, the running time does not increase the same way
for all algorithms.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
35

Example
¨ Assume an algorithm takes T(n) time for input size n.

Time Complexity If input becomes 2n Effect

O(1) T(2n) = T(n) No change
O(log n) T(2n) ≈ T(n) + 1 Very small increase
O(n) T(2n) = 2T(n) Time doubles
O(n²) T(2n) = 4T(n) Time becomes four times
O(n³) T(2n) = 8T(n) Time becomes eight times

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

36

Example
¨ Suppose an algorithm takes 1 second for n = 100.

Complexity Time for n = 200

O(n) 2 seconds
O(n²) 4 seconds
O(n³) 8 seconds

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

37

Worst-Case, Best-Case, and Average-Case Efficiencies:

¨ Some algorithms’ running time depends not only on input size (n) but also on the
specific input values, as seen in sequential search.

¨ In sequential search, elements are checked one by one until the key is found or the
list is exhausted.

¨ The efficiency of sequential search varies depending on the key’s position

(beginning, middle, end, or not present).

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

38

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

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

39

¨ Worst-case efficiency measures the maximum running time for any input of size n
and provides an upper bound on an algorithm’s performance (e.g., sequential
search: Cworst(n) = n ).

¨ Best-case efficiency measures the minimum running time for inputs of size n (e.g.,
sequential search: Cbest(n) = 1 ), but it is generally less important than worst-case
analysis.

¨ Average-case efficiency calculates expected running time based on assumed

probability distributions of inputs; it is more realistic but harder to analyze.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

40

Recapitulation of the Analysis Framework:

Main points of the framework outlined above.

¨ Both time and space efficiencies are measured as functions of the algorithm’s input
size.

¨ Time efficiency is measured by counting the number of times the algorithm’s basic
operation is executed. Space efficiency is measured by counting the number of
extra memory units consumed by the algorithm.

¨ The efficiencies of some algorithms may differ significantly for inputs of the same
size. For such algorithms, we need to distinguish between the worst-case, average-
case, and best-case efficiencies.

¨ The framework’s primary interest lies in the order of growth of the algorithm’s
running time (extra memory units consumed) as its input size goes to infinity.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
 Efficiency or Complexity of an
41
Algorithm
¨ 1. Space Efficiency (Space Complexity): Amount of space required by an
algorithm to solve the problem.

S(P) = C + SP (instance)
¨ S -> Space

¨ P -> Problem

¨ S(P) -> Space complexity of a problem

¨ C -> Independent constant variable (Space required to store the local variables)

¨ Sp(instance) -> Dependent variable part (Space required to store the auxiliary
variable)

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

42

Example1:
¨ Algorithm sum (a, b)
¨ // Input: 2 number a & b
¨ //Output: Summation of a & b
¨ return a+ b

¨ Solution: S(P) = C + SP (instance)

¨ C= 1+1 { Here as a and b are independent variables, each have value 1}

¨ C=2
¨ Sp(instance) = 0 { Because here there are no dependent variables }

¨ S(P) = 2 +0 = 2 = O(1) So, space complexity of this problem is a constant.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
43

Example2:
¨ Algorithm Arraysum (A, n)
¨ // Input: An array of elements of size n
¨ //Output: Summation of array elements

¨ sum <- 0
¨ for i <- 0 to n-1 do
¨ sum <- sum +A[i]
¨ return sum

Solution: S(P) = C + SP (instance)

¨ C= 1+1 { Here as sum and n are independent variables, each have value 1 }
¨ C=2

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

44

¨ Sp(instance) = 10 * n { Assume there are 10 elements in an array. }

¨ Sp(instance) = 10n

¨ S(P) = C + SP (instance)
¨ S(P) = 2 + 10n
¨ S(P) = 10n { This is because in between 2 and 10n, the 10n is the bigger one}
¨ S(P) = O(n)

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

45

¨ 2. Time Efficiency (Time Complexity): Indicates how fast the algorithm runs.

The time efficiency depends on:

¨ System on which its been executed

¨ Programming language used
¨ Compiler used

As the above parameter varies greatly the time complexity cannot be calculated.

So, to find the time complexity, we calculate how many times the basic operation gets
executed.
T(n) = Cop * C(n)
Cop = Time taken for one execution of the basic operation.
C(n) = Function expresses, how many times the basic operation is been executed.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
46

¨ Basic operation: Most important operation of the algorithm , i.e the operation
contributing the most of the total running time.

¨ Depending upon how many times the basic operation gets executed for an
particular input, the time complexity of an algorithm is expressed as follows:

¨ Best Case: The minimum number of times the basic operation is executed for a
given input size.

Example: linear search

Search for 10 in the list: [10, 18, 25, 30, 42]
Here the Best case is O(1)

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

47

¨ Worst Case: The maximum number of times the basic operation is executed for a
given input size.

Example: linear search

Search for 42 in the list: [10, 18, 25, 30, 42]
Here the Best case is O(n)

¨ Average Case: The average number of times the basic operation is executed for a
given input size.

Example: Search for an element in the list: [5, 12, 18, 25, 30]
¨ Assume the element to be searched is equally likely to be at any position.
• If it is at:
• position 1 → 1 comparison
• Position 2 → 2 comparisons
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
48

• Position 3 → 3 comparisons
• Position 4 → 4 comparisons
• Position 5 → 5 comparisons

¨ Average number of comparisons: 1+2+3+4+5/5 = 15/5 = 3

¨ So, in the average case, linear search requires (n + 1) / 2 comparisons, which is

proportional to n.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Asymptotic Notations and Basic
49
Efficiency Classes
¨ Algorithm efficiency is evaluated based on the order of growth of its basic
operation count, rather than exact running time.

¨ To compare growth rates, three asymptotic notations are used: Big oh (O), Big
Omega (Ω), and Big Theta (Θ).

¨ In analysis, t(n) usually represents an algorithm’s running time (or basic operation
count), while g(n) is a simpler function used for comparison.

¨ These notations help classify and rank algorithms according to how their running
time grows as input size n increases.

¨ t (n) will be an algorithm’s running time (usually indicated by its basic operation
count C(n)), and g(n) will be some simple function to compare with the count.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
 Efficiency class of algorithm
Class Name Examples
50
1 constant Best case scenario of the linear search
log n logarithmic worst case scenario of binary search and in a complete BST to
perform a search operation.
n linear Worst case scenario of linear search and Worst case scenario of
search in a BST
n log n linearithmic merge sort and quick sort (best case)
n2 quadratic Bubble sort and selection sort
n3 cubic multiplication of 2 matrices
2n exponential n queens problem and subset problem

n! factorial If we are generating all permutation to solve the Knapsack

problem.
Efficiency class in an ascending order

Constant < log n < n < n log n < n2 < n3 ….< n4 <n!
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26
51

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Asymptotic Notation
52

¨ To compare and rank the order of growth of a function (which expresses the time
complexity of an algorithm), we use asymptotic notation.

The 5 different types are as follows:

Name Symbols Numerical

operators
Big oh O <=
Big omega Ω >=
Big Theta Θ =
Small oh o <
Small omega >

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

53

¨ Assume t(n) and g(n) be two non-negative functions on a set of natural numbers.

¨ t(n) – Actual time taken by an algorithm

¨ g(n) – sample function used to compare the value with t(n)

Big oh (O) Notation

DEFINITION 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 values of n, i.e., if there
exist some positive constant c and some nonnegative integer n0 such that

t(n) ≤ c * g(n) for all n ≥ n0

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

54

¨ t(n) grows with the same rate or lesser rate with the g(n)

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

55

Example:
¨ t(n) = 3n + 2
¨ g(n) = n

¨ According to definition, in order to have t(n) = O(g(n) )

¨ t(n) <= c g(n)

¨ 3n + 2<= c. n // After the substitution
¨ // Check for what value of c and n0 the above equation is valid
For C=1 3n + 2<= c. n False
3n + 2<= n
For C=2 3n + 2<= c. n False
3n + 2<= 2n
For C=3 3n + 2<= c. n False
3nof+CSE,
Dr. Vikhyath K B, Dept 2<=Dr.3nHNNCE, Bengaluru 560060 16/03/26
56

For c=4
¨ 3n + 2<= 4n // This may be true

Now check for n0 also

For n=1 3n + 2<= 4n False

5<=4
For n=2 3n + 2<= 4n True
8<=8

Therefore no value is 2
We can write 3n + 2 = O(n)

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

57

Efficiency class in an ascending order

Constant < log n < n < n log n < n2 < n3 ….< n!

Comparative operator used here is ≤

n2 O ( n3 ) True
n2 O ( n2 ) True
n3 O ( n! ) True
n2 O ( log n) False

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

58

Big omega Ω
DEFINITION: A function t(n) is said to be in Ω (g(n)), denoted t(n) ∈ Ω(g(n)), if t(n)
is bounded below by some positive constant multiple of g(n) for all large n, i.e., if
there exist some positive constant c and some nonnegative integer n0 such that

t(n) ≥ c g(n) for all n ≥ n0

Example:
¨ t(n) = 3n + 2
¨ g(n) = n

¨ According to definition, in order to have t(n) = Ω (g(n) )

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

59

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

60

¨ t (n) ≥ c g (n)
¨ 3n + 2 ≥ c. n // After the substitution
¨ // Check for what value of c and n0 the above equation is valid

For C=1 3n + 2 ≥ c. n True

3n + 2 ≥ n
For C=2 3n + 2 ≥ c. n True
3n + 2 ≥ 2n
For C=3 3n + 2 ≥ c. n True
3n + 2 ≥ 3n
For C=4 3n + 2 ≥ c. n False
3n + 2 ≥ 4n

¨ Therefore c = 3

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

61

¨ Now check for n0 also

For n=1 3n + 2 ≥ 3n True
5≥3
For n=2 3n + 2 ≥ 3n True
8≥6
For n=3 3n + 2 ≥ 3n True
11 ≥ 9

Therefore no value is 1
We can write 3n + 2 = Ω (n)

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

62

Efficiency class in an ascending order

Constant < log n < n < n log n < n2 < n3 ….< n!

Comparative operator used here is ≥

n2 Ω ( n3 ) False
n3 Ω ( n2 ) True
n! Ω (log n) True
2n Ω (n2 ) True
n3 Ω (3n) False

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

63

Big theta Θ
DEFINITION A function t (n) is said to be in Θ(g(n)), denoted t (n) ∈ Θ(g(n)), if t(n)
is bounded both above and below by some positive constant multiples of g(n) for all
large n, i.e., if there exist some positive constants c1 and c2 and some nonnegative
integer n0 such that

c2g(n) ≤ t(n) ≤ c1g(n) for all n ≥ n0

Example:
¨ t(n) = 3n + 2
¨ g(n) = n
¨ t(n) can contain any technique which has the same rate as g(n).
¨ According to definition, in order to have t(n) = Θ (g(n) )

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

64

¨ c2g(n) ≤ t(n) ≤ c1g(n)

¨ 3n +2 = Θ(n)
¨ c2 n ≤ 3n +2 ≤ c1 n

Observation:

¨ In this case 3n +2 ≤ c1 n
¨ c1 = 4 and n0 = 2

¨ In this case c2 n ≤ 3n +2
¨ c1 = 3 and n0 = 1

¨ By the analysis of the above, conclusion is n0 = 2

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

65

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Mathematical Analysis of Non-recursive
Algorithms
66

General Plan for Analyzing the Time Efficiency of Non-recursive Algorithms

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

2. Identify the algorithm’s basic operation. (As a rule, it is located in the inner- most
loop.)
3. 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.
4. Set up a sum expressing the number of times the algorithm’s basic operation is
executed.
5. Using standard formulas and rules of sum manipulation, either find a closed- form
formula for the count or, at the very least, establish its order of growth.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 EXAMPLE 1 Consider the problem of finding the value of
the largest element in a list of n numbers. For simplicity, we
assume that the list is implemented as an array.
67

¨ 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 in A

¨ maxval ← A[0]
¨ for i ← 1 to n − 1 do
¨ if A[i] > maxval
¨ maxval ← A[i]
¨ return maxval

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

68

1. Input size is n
2. Basic operation comparison is C
3. Let C (n) denotes the number of types the comparison gets executed.

4.

5. n-1-1+1 = n-1

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 EXAMPLE 2 Consider the element uniqueness problem: check whether all
the elements in a given array of n elements are distinct. This problem can be
solved by the following straightforward algorithm.
69

¨ ALGORITHM UniqueElements(A[0..n − 1])

¨ //Determines 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

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

70

1. Input size is n
2. Basic operation comparison is C
3. Let C (n) denotes the worst case scenario.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 EXAMPLE 3 Given two n × n matrices A and B, find the time efficiency of
the definition-based algorithm for computing their product C = AB. By
definition, C is an n × n matrix whose elements are computed as the scalar
(dot) products of the rows of matrix A and the columns of matrix B:
71

Where C[i, j] = A[i, 0] B[0, j] + . . . + A[i, k] B[k, j] + . . . + A[i, n − 1] B[n − 1, j]

for every pair of indices 0 ≤ i, j ≤ n − 1

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26

72

ALGORITHM MatrixMultiplication(A[0..n − 1, 0..n − 1], B[0..n − 1, 0..n − 1])

¨ //Multiplies two square matrices of order n by the definition-based algorithm

¨ //Input: Two n × n matrices A and B
¨ //Output: Matrix C = A B

¨ for i ← 0 to n − 1 do
¨ for j ←0 to n−1do
¨ C [i, j ] ← 0.0
¨ for k ← 0 to n − 1 do
¨ C[i, j]← C[i, j]+ A[i, k]∗ B[k, j]
¨ return C

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26

73

¨ The number of multiplications made for every pair of specific values of variables i
and j is

¨ and the total number of multiplications M(n) is expressed by the following triple
sum:

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26

74

¨ If we now want to estimate the running time of the algorithm on a particular

machine, we can do it by the product

T (n) ≈ cmM(n) = cmn3,

¨ where cm is the time of one multiplication on the machine in question. We would
get a more accurate estimate if we took into account the time spent on the
additions, too:

T (n) ≈ cmM(n) + caA(n) = cmn3 + can3 = (cm + ca)n3

¨ Where ca is the time of one addition

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26

 EXAMPLE 4 The following algorithm finds the number of binary digits
in the binary representation of a positive decimal integer.
75

¨ ALGORITHM Binary(n)

¨ //Input: A positive decimal integer n

¨ //Output: The number of binary digits in n’s binary representation

¨ count ← 1
¨ while n > 1 do
¨ count ← count + 1
¨ n ← ⌊n/2⌋
¨ return count

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

76

¨ It repeatedly divides n by 2
¨ Each division removes one binary digit
¨ The variable count keeps track of how many digits the number has in binary
Key observation

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

77

Number of iterations

¨ The loop runs approximately:

⌊log 2n⌋

But since count starts at 1, the final result is:

⌊log2n⌋+1
Example
¨ For n=13
¨ Binary: 1101 → 4 digits
¨ ⌊log213⌋+1=3+1=4

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 16/03/26

 Mathematical Analysis of Recursive
Algorithms
78

General Plan for Analyzing the Time Efficiency of Recursive Algorithms

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

2. Identify the algorithm’s basic operation.

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

4. Set up a recurrence relation, with an appropriate initial condition, for the number of
times the basic operation is executed.

5. Solve the recurrence or, at least, ascertain the order of growth of its solution.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26
 EXAMPLE 1 Compute the factorial function F (n) = n! for an arbitrary
nonnegative integer n.
79

¨ 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

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26

80

¨ We consider n itself as an indicator of this algorithm’s input size.

¨ The basic operation of the algorithm is multiplication, whose number of
executions we denote M(n).

¨ Base case: If n is 0 (zero) no multiplication is performed.

¨ Therefore succeeded in setting up the recurrence relation and initial condition for
the algorithm’s number of multiplications M(n):
M(n) = M(n-1) + 1 for n > 0
M (n) = M (0) = 0

¨ The function F (n) is computed according to the formula

F(n)=F(n−1).n for every n >= 0
F(0) = 1
¨ The number of multiplications M(n) needed to compute it must satisfy the equality
M(n) = M(n − 1) + 1 for n > 0
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26
81

Substitution Method
¨ M(n) = M(n − 1) + 1 substitute M(n − 1) = M(n − 2) + 1
¨ =[M(n−2)+1]+1=M(n−2)+2 substitute M(n−2) = M (n − 3)+1
¨ = [M (n − 3) + 1] + 2 = M (n − 3) + 3

General formula for the pattern: M(n) = M(n − i) + i

¨ The correctness of this formula should be proved by mathematical induction
¨ M(n) = M(n − 1) + 1 for n >= 0
¨ = M(n − i) + i
¨ =M( n – i) = 0 By the way Base case: M(0) = 0
¨ Therefore: n – i = 0
¨ n=i
¨ Therefore M(n) = M(n − 1) + 1 = M(n − i) + i = M(n − n) + n = 0 + n = n
¨ This is the time complexity of a recursive algorithm of a factorial (n)
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26
 EXAMPLE 2 : Tower of Hanoi puzzle. In this puzzle, we have n disks of different sizes that can
slide onto any of three pegs. Initially, all the disks are on the first peg in order of size, the largest
on the bottom and the smallest on top. The goal is to move all the disks to the third peg, using the
second one as an auxiliary, if necessary. We can move only one disk at a time, and it is forbidden
to place a larger disk on top of a smaller one.
82

Algorithm: TowerofHanoi(n, S, D, T)

¨ // Solves the Towerof Hanoi problem

¨ //Input: No. of disc’s = n, three pegs (towers) S, D, T
¨ //Output: All n discs stacked on D

¨ if n==1
Move a disc from S to D
¨ else
Towerofhanoi(n-1, S, T, D)
Move nth disc from S to D
Towerofhanoi(n-1, T, D, S)

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26

83

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26

84

¨ Basic Operation: Movement of disc = M

¨ Base case: if n=1 we do 1 move from source to destination
¨ M(n) = M(1) = 1
¨ if n > 1 then
¨ M(n) = M(n−1) + 1 + M(n−1) for n > 1 According to the pseudocode else-part
¨ M(n) = 2 M(n−1) + 1

Use the substitution method

¨ M(n) = 2 M (n-1) + 1 = 2 (2 M (n-2) + 1 ) + 1 = 4 M (n-2) + 2 + 1

¨ = 4 (2 M (n-3) + 1 ) + 2 + 1 = 8 M (n-3) + 4 + 2 + 1 = 23 M (n-3) + 22 + 21 + 20
¨ = 2i M (n-i) + 2i-1 + 2i-2 + …+ 21 + 20

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26

85

Consider the base case

¨ M(n-i) = 1
¨ n-i=1
¨ i=n–1

¨ = 2i M (n-i) + 2i-1 + 2i-2 + …+ 21 + 20

Substitute i = n - 1

¨ = 2i M (n-i) + 2i-1 + 2i-2 + 2i-3 …+ 21 + 20 = 2n-1 M( 1) + 2n-2 + 2n-3 + 2n-4 + ..+ 20

¨ = 2n-1 + 2n-2 + 2n-3 + 2n-4 + ..+ 21 + 20
¨ = 2n – 1 According to the rule

¨ This is the time complexity of Tower of Hanoi.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 18/03/26
86

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26

 EXAMPLE 3: Recursive version of algorithm finds the number of
binary digits in the binary representation of a positive decimal
integer.
87

ALGORITHM BinRec(n)

¨ //Input: A positive decimal integer n

¨ //Output: The number of binary digits in n’s binary representation

¨ if n = 1 return 1
¨ else return BinRec(⌊n/2⌋) + 1

¨ Let us set up a recurrence and an initial condition for the number of additions A(n)
made by the algorithm.

¨ The number of additions made in computing BinRec(⌊n/2⌋) is A(⌊n/2⌋), plus one

more addition is made by the algorithm to increase the returned value by 1. This
leads to the recurrence as below:
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 24/03/26
88

A(n) = A(⌊n/2⌋) + 1 for n > 1

¨ Since the recursive calls end when n is equal to 1 and there are no additions made
then, the initial condition is

A(1) = 0

¨ Assume n = 2k gives a correct answer about the order of growth for all values of n.

¨ A(n) = A(⌊n/2⌋) + 1 for n > 1

¨ A(n) = A(⌊2k/21⌋) + 1
¨ A(n) = A(⌊2k-1⌋) + 1 for k > 0

¨ As we know 20 = 1 , so A(1) = 0
¨ A(20) = A(1) = 0
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 24/03/26
89

Substitutions method:
¨ A(2k) = A(2k−1) + 1 substitute A(2k−1) = A(2k−2) + 1
¨ A(2k) = [A(2k−2) + 1] + 1 = A(2k−2) + 2 substitute A(2k−2) = A(2k−3) + 1
¨ A(2k) = [A(2k−3) + 1] + 2 = A(2k−3) + 3
...
¨ A(2k) = A(2k−i) + i

The Base case: 2k–i = 20

k-i = 0
i= k
¨ A(2k) = A(2k−k) + k.
Thus, we end up with
¨ A(2k) = A(20) + k = A(1) + k = 0 + k = k
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 24/03/26
90

¨ or, after returning to the original variable n = 2k and hence k = log2 n

A(n) = log2 n ∈ Θ (log n)

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 24/03/26

 Useful Property Involving the
Asymptotic Notations
91

General property: The following property, in particular, is useful in analysing algorithms

that comprise two consecutively executed parts.

THEOREM: If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)) then

t1(n) + t2(n) ∈ O(max{g1(n), g2(n)})

¨ (The analogous assertions are true for the Ω and Θ notations as well.)

PROOF The proof extends to orders of growth the following simple fact about four
arbitrary real numbers a1, b1, a2, b2: if a1 ≤ b1 and a2 ≤ b2, then a1 + a2 ≤ 2 max{b1, b2}.

¨ Since t1(n) ∈ O(g1(n)), there exist some positive constant c1 and some non-negative
integer n1 such that
t1(n) ≤ c1g1(n) for all n ≥ n1
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26
92

¨ Similarly, since t2(n) ∈ O(g2(n))

t2(n) ≤ c2g2(n) for all n ≥ n2

Let us denote c3 = max{c1, c2} and consider n ≥ max{n1, n2} so that we can use both
inequalities. Adding them yields the following:

¨ t1(n) + t2(n) ≤ c1g1(n) + c2g2(n)

≤ c3g1(n) + c3g2(n) = c3[g1(n) + g2(n)]

≤ c32 max{g1(n), g2(n)}

¨ Hence, t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}), with the constants c and n0 required by
the O definition being 2c3 = 2 max{c1, c2} and max{n1, n2}, respectively.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26

93

¨ 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:

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26

 Selection Sort
94

¨ Selection sort starts 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 :

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26

95

¨ After n − 1 passes, the list is sorted.

¨ Here is pseudocode of this algorithm, which, for simplicity, assumes that the list is
implemented as an array:

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

¨ //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
ifA[j] < A[min] min ← j
swap A[i] and A[min]
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26
96

¨ As an example, the action of the algorithm on the list 89, 45, 68, 90, 29, 34, 17 is
illustrated as below.

FIGURE 3.1 : Example of sorting with selection sort. Each line corresponds to one
iteration of the algorithm, i.e., a pass through the list’s tail to the right of the vertical
bar; an element in bold indicates the smallest element found. Elements to the left of the
vertical bar are in their final positions and are not considered in this and subsequent
iterations.
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 25/03/26
97

¨ The input size is given by the number of elements n

¨ The basic operation is the key comparison A[j ] < A[min].
¨ The number of times it is executed depends only on the array size and is given by
the following sum:

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 25/03/26

98

¨ Thus, selection sort is a Θ(n2) algorithm on all inputs. Note, however, that the
number of key swaps is only Θ(n), or, more precisely, n−1(one for each repetition
of the i loop). This property distinguishes selection sort positively from many other
sorting algorithms.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26

 Bubble Sort
99

¨ Another brute-force application to the sorting problem is to compare adjacent

elements of the list and exchange them if they are out of order.

¨ By doing it repeatedly, we end up “bubbling up” the largest element to the last
position on the list.

¨ The next pass bubbles up the second largest element, and so on, until after n − 1
passes the list is sorted.

¨ Pass i (0 ≤ i ≤ n − 2) of bubble sort can be represented by the following diagram:

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26

100

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 ]

¨ The action of the algorithm on the list 89, 45, 68, 90, 29, 34, 17 is illustrated as
below:

¨ The number of key comparisons for the bubble-sort version given above is the
same for all arrays of size n; it is obtained by a sum that is almost identical to the
sum for selection sort:
Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 22/03/26
101

Example:

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 23/03/26

102

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 23/03/26

 Sequential Search
103

¨ Sequential search: 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.

¨ Another straightforward improvement can be incorporated in sequential search if a

given list is known to be sorted: searching in such a list can be stopped as soon as
an element greater than or equal to the search key is encountered.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 23/03/26

104

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

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 23/03/26

 Brute-Force String Matching
105

¨ Given a string of n characters called the text and a string of m characters (m ≤ n)

called the pattern, find a substring of the text that matches the pattern.

¨ To put it more precisely, we want to find i the index of the leftmost character of the
first matching substring in the text such that ti = p0,..., ti+j = pj, ..., ti+m−1= pm−1:

¨ If matches other than the first one need to be found, a string-matching algorithm
can simply continue working until the entire text is exhausted.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 23/03/26

106

¨ A brute-force algorithm for the string-matching problem is quite obvious: align the
pattern against the first m characters of the text and start matching the
corresponding pairs of characters from left to right until either all the m pairs of
the characters match or a mismatching pair is encountered.

¨ In the latter case, shift the pattern one position to the right and resume the
character comparisons, starting again with the first character of the pattern and
its counterpart in the text.

¨ Note: The last position in the text that can still be a beginning of a matching
substring is n − m (provided the text positions are indexed from 0 to n − 1).

¨ Beyond that position, there are not enough characters to match the entire pattern;
hence, the algorithm need not make any comparisons there.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 23/03/26

107

ALGORITHM BruteForceStringMatch(T [0..n − 1], P [0..m − 1] )

¨ //Implements brute-force string matching

¨ //Input: An array T [0..n − 1] of n characters representing a text and an array
¨ // P [0..m − 1] of m characters representing a pattern
¨ //Output: The index of the first character in the text that starts a matching substring
or −1 if the search is unsuccessful
¨ for i ← 0 to n − m do
j←0
while j < m and P[j] = T[i + j] do
j←j+1
if j =m return i
¨ return −1

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 23/03/26

108

Example of brute-force string matching.

Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 23/03/26

16/03/26 Dr. Vikhyath K B, Dept of CSE, Dr. HNNCE, Bengaluru 560060 109