1

Module-1

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.

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)

1. Introduction
1.1. What is an algorithm?
 Algorithm is a step-by-step calculation of specific problem. (OR)
 An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a
required output for any legitimate input in a finite amount of time.

Figure: 1.1. The notion of the algorithm.

 An algorithm is a finite set of unambiguous instruction for solving problem.

 All algorithms must satisfy the following criteria.
o Input: Zero or more quantities are externally supplied.
o Output: At least one quantity is produced.
o Definiteness: Each instruction is clear and unambiguous.
o Finiteness: Algorithm should terminate after a finite number of steps.
o Effectiveness: Every instruction must be very basic so the people can easily understand. It
must be feasible
 Example:
 Euclid‟s algorithm is gcd(m, n) = gcd(n, m mod n),i.e., gcd(60, 24) can be
computed as follows:
 gcd(60, 24) = gcd(n, m mod n)
 = gcd(24, 60 mod 24)
 = gcd(24,12)
 gcd(24, 12) = gcd(n, m mod n)
 = gcd(12, 24 mod 12)
 =gcd(12, 0)
 gcd(12, 0) = gcd(n, m mod n)
 =gcd(12, 0 mod 12)
 = 12
 Euclid’s algorithm for computing gcd(m, n)

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 2

Module-1
o
Step 1: If n = 0, return the value of m as the answer and stop; otherwise, proceed to Step
2.
o Step 2: Divide m by n and assign the value of the remainder to r.
o Step 3: Assign the value of n to m and the value of r to n. Go to Step 1.
 ALGORITHMEuclid (m, n) (Pseudocode)
o //Computes gcd(m, n) by Euclid‟s algorithm
o //Input: Two nonnegative, not-both-zero integers m and n
o //Output: Greatest common divisor of m and n
o while n ≠ 0 do
o r ←m mod n
o m ←n
o n ←r
o return m
 Expressing Algorithms
o English description
o Pseudo-code
o High-level programming language
 Characteristic of Algorithms
o Step by step description.
o Anybody can easily understand.
o Theoretical explanation of program
1.2. Fundamentals of Algorithmic Problem Solving
 A sequence of steps of designing and analyzing an algorithm as shown in the figure (Figure
1.2).
1.2.1. Understanding the Problem
 Understand the given problem completely before designing an algorithm.
 Read the problem‟s description carefully and ask questions if you have any doubts about the
problem,
 Identify the problem types and use existing algorithm to find solution.
 Input (instance) to the problem and range of the input get fixed.
1.2.2. Ascertaining the Capabilities of the Computational Device
 In random-access machine (RAM), the instructions are executed one after another, one
operation at a time. Accordingly, algorithms designed to be executed on such machines are
called sequential algorithms.
 In some newer computers, operations are executed concurrently, i.e., in parallel. Algorithms
that take advantage of this capability are called parallel algorithms.
 Choice of computational devices like Processor and memory is mainly based on space and
time efficiency.
1.2.3. Choosing between Exact and Approximate Problem Solving
 Exact Algorithm: An algorithm used to solve the problem exactly and produce correct result.
o Example: Branch and Bound, Traveling Salesman Problem (TSP).
 Approximation algorithm: An algorithmcannot be solved exactly formost of their instances.

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 3

Module-1
 Example:Extracting Square Roots, Solving Nonlinear Equations, and Evaluating Definite
Integrals.

Figure: 1.2 Algorithm design and analysis process.

1.2.4. 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.
1.2.5. Designing an Algorithm and Data Structures
 Algorithms and Data Structures are independent, but they are combined to develop program.
Hence the choice of proper data structure is required before designing the algorithm.
 Algorithms + Data Structures = Program
 Implementation of algorithm is possible only with the help of Algorithms and Data Structures.
 Algorithmic strategy / technique / paradigm is a general approach by which many problems
can be solved algorithmically. E.g., Brute Force, Divide and Conquer, Dynamic Programming,
Greedy Technique and soon.
1.2.6. Methods of Specifying an Algorithm
 We can express an algorithm many ways, including natural language, flow charts,
pseudocode, and of course, actual programming languages.
 Pseudocode and flowchart are the two options that are most widely used nowadays for
specifying algorithms.
o Natural Language:

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 4

Module-1
 It is very simple and easy to specify an algorithm using natural language. But
many times, specification of algorithm by using natural language is not clear
and thereby we get brief specification.
 Example: An algorithm to perform addition of two numbers.
o Step 1: Read the first number, say a.
o Step 2: Read the second number, say b.
o Step 3: Add the above two numbers and store the result in c.
o Step 4: Display the result from c.
 Such a specification creates difficulty while implementing it. Hence many
programmers prefer to have specification of algorithm by means of
Pseudocode.
o Pseudocode:
 It is a mixture of a natural language and programming language construct.
 Pseudocode is usually more precise than natural language.
 Conditional statements are used.
 Example: ALGORITHM Sum (a,b)
o //Problem Description: This algorithm performs addition of
two numbers
o //Input: Two integers a and b
o //Output: Addition of two integers
o c←a+b
o return c
o Flowchart:
 Flowchart is a graphical representation of an algorithm. It is a method of
 expressing an algorithm by a collection of connected geometric shapes
 containing descriptions of the algorithm‟s steps.

Figure: 1.3 Flow Chart Symbol

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S
 5

Module-1
 Example: Flowchart for addition of TWO Numbers

Figure: 1.4 Flowchart for addition of two numbers

1.2.7. Proving an Algorithm’s Correctness
 Once an algorithm has been specified, you must prove its correctness.
 An algorithm must yield 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).
 A common technique for proving correctness is to use mathematical induction because an
algorithm‟s iterations provide a natural sequence of steps needed for such proofs.
 The notion of correctness for approximation algorithms is less straightforward than it is for
exact algorithms. The error produced by the algorithm should not exceed a predefined limit.
1.2.8. Analyzing an Algorithm
 An algorithm‟s important factor is efficiency.
 There are two kinds of algorithm efficiency: Time efficiency and space efficiency.
o Time efficiency: Indicating how fast the algorithm runs.
o Space efficiency: Indicating how much extra memory it uses.
 The efficiency of an algorithm is determined by measuring both time efficiency and space
efficiency.
 So, factors to analyze an algorithm are:
o Time efficiency of an algorithm
o Space efficiency of an algorithm
o Simplicity of an algorithm
o Generality of an algorithm
1.2.9. Coding an Algorithm
 The coding / implementation of an algorithm is done by a suitable programming language like
C, C++,JAVA.
 The transition from an algorithm to a program can be done either incorrectly or very
inefficiently. Implementing an algorithm correctly is necessary.
 The Algorithm power should not reduce by in efficient implementation.
 Standard tricks like computing a loop‟s invariant (an expression that does not change its value)
outside the loop, collecting common subexpressions, replacing expensive operations by cheap
ones, selection of programming language and so on should be known to the programmer.

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 6

Module-1
 Typically, such improvements can speed up a program only by a constant factor, whereas a
better algorithm can make a difference in running time by orders of magnitude. But once an
algorithm is selected, a 10–50% speedup may be worth an effort.
 It is very essential to write an optimized code (efficient code) to reduce the burden of
compiler.
2. Fundamentals of the Analysis of Algorithm Efficiency
 The efficiency of an algorithm can be in terms of time and space.
 Time efficiency, also called time complexity, indicates how fast an algorithm in question runs.
 Space efficiency, also called space complexity, refers to the amount of memory units required
by the algorithm in addition to the space needed for its input and output.
2.1. Analysis of Framework
 The algorithm analysis framework consists of the following:
o Measuring an Input‟s Size
o Units for Measuring Running Time
o Orders of Growth
o Worst-Case, Best-Case, and Average-Case Efficiencies
2.1.1. Measuring an Input’s Size
 An algorithm‟s efficiency is defined as a function of some parameter n indicating the
algorithm‟s input size. In most cases, selecting such a parameter is quite straightforward.
o For example, it will be the size of the list for problems of sorting, searching.
 For the problem of evaluating a polynomial p(x) = anxn+ . . . + a0 of degree n, the size of the
parameter will be the polynomial‟s degree or the number of its coefficients, which is larger by
1 than its degree.
 In computing the product of two n × n matrices, the choice of a parameter indicating an input
size does matter.
 Consider a spell-checking algorithm. If the algorithm examines individual characters of its
input, then the size is measured by the number of characters.
 In measuring input size for algorithms solving problems such as checking primality of a
positive integer n. the input is just one number.
 The input size by the number b of bits in the n‟s binary representation is b=(log2n) +1.
2.1.2. Units for Measuring Running Time
 Some standard unit of time measurement such as a second, or millisecond, and so on can be
used to measure the running time of a program after implementing the algorithm.
 Drawbacks:
o Dependence on the speed of a particular computer.
o Dependence on the quality of a program implementing the algorithm.
o The compiler used in generating the machine code.
o The difficulty of clocking the actual running time of the program.
 So, we need metric to measure an algorithm‟s efficiency that does not depend on these
extraneous factors.
 One possible approach is to count the number of times each of the algorithm‟s operations is
executed. This approach is excessively difficult.

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 7

Module-1
 The most important operation (+, -, *, /) of the algorithm, called the basic operation.
Computing the number of times the basic operation is executed is easy. The total running time
is determined by basic operations count.
2.1.3. Orders of Growth
 A difference in running times on small inputs is not what really distinguishes efficient
algorithms from inefficient ones.
 For example, the greatest common divisor of two small numbers, it is not immediately clear
how much more efficient Euclid‟s algorithm is compared to the other algorithms, the
difference in algorithm efficiencies becomes clear for larger numbers only.
 For large values of n, it is the function‟s order of growth that counts just like the Table 1.1,
which contains values of a few functions particularly important for analysis of algorithms.

Table: 1.1Values (approximate) of several functions important for analysis of algorithms

2.1.4. Worst-Case, Best-Case, and Average-Case Efficiencies
Let consider the algorithm of sequential search algorithm with some search element K in a list of n
elements.

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

//Searches for a given value in each 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 Kor -1 if there are no matching
//elements
i ←0
while I < n and A[i] ≠ K do
i ←i + 1
if i<nreturn i
else return -1
a. Worst Case:
o No matching of the first elements in the list.
o The first matching element can be found at last on the list.

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 8

Module-1
o No matching of the elements in the list.
o Worst-Case Efficiency:
 The worst-case efficiency of an algorithm is its efficiency for the worst-case
input of size n.
 The algorithm runs the longest among all possible inputs of that size.
 For the input of size n, the running time is Cworst(n) = n.
b. Best Case:
o There is matching of elements at first on the list.
o Best Case Efficiency:
 The best-case efficiency of an algorithm is its efficiency for the best-case
input of size n.
 The algorithm runs the fastest among all possible inputs of that size n.
 In sequential search, If we search a first element in list of size n. (i.e. first
element equal to a search key), then the running time is Cbest(n) = 1.
c. Average Case:
o The Average case efficiency lies between best case and worst case.
o Average Case Efficiency:
 The Average case efficiency lies between best case and worst case.
 To analyze the algorithm‟s average case efficiency, we must make some
assumptions about possible inputs of size n.
 The standard assumptions are that
o The probability of a successful search is equal to p (0 ≤ p ≤ 1) and
o The probability of the first match occurring in the ith position of the
list is the same for every i.

d. Amortized Efficiency:
o It applies not to a single run of an algorithm but rather to a sequence of operations
performed on the same data structure.
2.2. Asymptotic Notations and Basic Efficiency Classes
 Asymptotic Notations are mathematical tools used to describe the behavior of algorithms in
terms of time or space complexity as the input size grows. This is also known as an algorithm's
growth rate.
 The asymptotic notations are:
o Big-Oh notation (O)
o Omega notation (Ω)
o Theta notation (Ꝋ)

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 9

Module-1
 t(n) and g(n) can be any nonnegative functions defined on the set of natural numbers. In the
context we are interested in, 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 the count with.
2.2.1. Informal Introduction
 Informally, O(g(n)) is the set of all functions with a lower or same order of growth as g(n) (to
within a constant multiple, as n goes to infinity). Thus, to give a few examples, the following
assertions are all true:

 Indeed, the first two functions are linear and hence have a lower order of growth than g(n) =
n2, while the last one is quadratic and hence has the same order of growth as n2. On the other
hand.

Indeed, the function n3 and 0.00001n3are both cubic and hence have a higher order of growth
than n2, and so has the fourth-degree polynomial n4+n+1.
The second notation, Ω(g(n)) stands for the set of all functions with a higheror same order of
growth as g(n) (to within a constant multiple, as n goes to infinity).For example,

Finally, Θ(g(n)) is the set of all functions that have the same order of growth as g(n) (to within
a constant multiple, as n goes to infinity). Thus, every quadratic function an2+ bn + c with a>0
is in Θ(n2).
2.2.2. 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 n, i.e., if there exist some positive constant c
and some nonnegative integer n0such that
t (n) ≤ cg(n) for all n ≥ n0

Figure: 1.5. Big-oh notation: t (n) ∈ O(g(n)).

Example: Prove 100n+5 ∈ O(n2)
Solution:

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 10

Module-1
Thus, as values of the constants c and n0required by the definition, we can take101 and 5,
respectively.
Another way
100n+5 = c*g(n2)
Let n = 1, then
100(1)+5 = c(12)
100+5 = c(1)
105 = c
Here c=105 and n0 = 1.
Example: Consider function f(n) = 2n + 2 and g(n) = n2 . Then to find some constant C, so that
f(n) ≤ c * g(n). As f(n) = 2n + 2 and g(n) = n2
Solution:
Find c
 for n = 1 then
f(n) = 2n +2
= 2(1) + 2
=2+2
f(n) = 4
Then, g(n) = n2
= (1)2
g(n) = 1
Therefore f(n) > g(n)
 If n = 2 then,
f(n) = 2(2) +2
=4+2
f(n) = 6
And then, g(n) = n2
=(2)2
g(n) = 4
Therefore f(n) > g(n)
 If n = 3 then,
f(n) = 2(3) +2
=6+2
f(n) = 8
and then, g(n) = n2
= (3)2
g(n) = 9
Therefore f(n) < g(n)
Hence we can conclude that for n > 2, we obtain f(n) < g(n)

2.2.3. Big Omega notation (Ω notation)

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 11

Module-1
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) ≥ cg(n) for all n ≥ n0

Figure: 1.6. Big-omega notation: t (n) ∈ Ω(g(n)).

Example: Prove that n ∈Ω(n2)
3

Solution:
n3 ≥ (n2), for all n ≥ 0
i.e., we can select c = 1 and n0 = 0.
Example: f(n) = 2n2 + 5 and g(n) = 7n
Solution:
Then if n = 0
f(n) = 2(0)2 + 5
=5
g(n) = 7(0)
=0
Therefore, f(n) > g(n)
but if n = 1
f(n) = 2(1)2 + 5
=2+5
f(n) = 7
then g(n) = 7n
= 7(1)
g(n) = 7
Therefore, f(n) = g(n)
but if n = 2
f(n) = 2(2)2 + 5; 2 * 4 + 5
=8+5
f(n) = 13
then g(n) = 7n
= 7(2)
g(n) = 14

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 12

Module-1
Therefore, f(n) < g(n)
but if n = 3
f(n) = 2(3)2 + 5
=2*9+5
= 18 + 5
f(n) = 23
then g(n) = 7n
= 7(3)
g(n) = 21
Therefore, f(n) > g(n)
 Thus for n > 3 we get f(n) > c * g(n)
 It can be represented as 2n2 + 5 ϵ Ω (n)
2.2.4. Theta notation (Θ notation)
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)

Figure: 1.7. Big-Theta notation: t (n) ∈ Θ (g(n)).

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 13

Module-1

2.2.5. Basic Efficiency Classes

In the analysis and design of algorithms, efficiency is categorized based on time and space
complexity. The basic efficiency classes, also known as complexity classes, describe how an
algorithm's performance scales with input size. Here are the main efficiency classes:
Sl. Class Name Comments
No.
 May be a best case.
 The algorithm runs in a fixed amount of time, regardless of
1 1 Constant
input size.
 Example: Accessing an element in an array by index (arr[i]).
 The running time grows logarithmically as the input size
2 logn Logarithmic increases.
 Example: Binary search.
 scan a list of size n
3 n Linear  The running time increases proportionally to the input size.
 Example: Iterating through an array.
 Many divide-and-conquer algorithms
4 nlogn Linearithmic  Common in efficient sorting algorithms.
 Example: Merge Sort, Quick Sort (average case).
 The time increases quadratically with input size.
5 n2
Quadratic  Two embedded loops
 Example: Bubble Sort, Insertion Sort (worst case).
 The running time increases cubically with input size.
 Three embedded loops
6 n3 Cubic
 Example: Some brute-force solutions in graph algorithms (e.g.,
Floyd-Warshall algorithm for shortest paths).
 The time doubles with each additional input element.
 All subsets of an n-element set.
7 2n Exponential
 Example: Recursive Fibonacci, brute-force solutions for NP-
complete problems.
 The worst-case scenario where runtime grows factorially.
8 n! Factorial  All permutations of an n-element set.
 Example: Traveling Salesman Problem (brute-force solution).

These efficiency classes help in selecting the best algorithm for a problem based on the trade-offs
between speed and computational resources.
2.3. Mathematical Analysis of Nonrecursive Algorithms
 When analyzing the time efficiency of nonrecursive algorithms in the context of the goal is to
determine the computational cost of the algorithm in terms of its input size.

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 14

Module-1
 This process helps in understanding the behavior of the algorithm in terms of how quickly it
grows as the size of the input increases.
2.3.1. General Plan for Analyzing the Time Efficiency of Nonrecursive 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.
 Set up a sum expressing the number of times the algorithm‟s basic operation is executed.
 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.
 Example-1:
o Consider the problem of finding the value of the largest element in a list of n
numbers. Assume that the list is implemented as an array for simplicity.
 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
o maxval ←A[i]
 return maxval
 Algorithm Analysis:
o The obvious measure of an input‟s size here is the number of elements in the array,
i.e., n.
o The basic operations are going to be executed in the algorithm; here loop is the basic
operation.
o There are two operations in the loop‟s body
 The comparison A[i]> maxval
 The assignment max val←A[i].
o The comparison operation is considered as basic operation in this algorithm.
o The comparison is executed on each repetition of the loop and the assignment is not
repeatedly executed.
o The number of comparisons will be the same for all arrays of size n.
o Therefore, there is no need to distinguish among the worst, average, and best cases
here.
o Let C(n) the number of times this comparison is executed and try to find a formula
expressing it as a function of size n. The algorithm makes one comparison on each
execution of the loop, which is repeated for each value of the loop‟s variable i within
the bounds 1 and n - 1, inclusive. Therefore, we get the following sum for C(n):

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 15

Module-1
n 1
c ( n)  1
i 1

o i.e., Sum up 1 in repeated n-1 times

n 1
c ( n)  1  n  1   ( n)
i 1

 Example-2:
o 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.
 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
 Algorithm Analysis:
o The measure of the input‟s size n (array[n]).
o The innermost loop contains a single operation (the comparison of two elements)), it
considered as basic operation of this algorithms.
o The number of element comparisons depends not only on n but also on whether there
are equal elements in the array and, if there are, which array positions they occupy.
Then, will limit our investigation to the worst case only.
o One comparison is made for each repetition of the innermost loop, i.e., for each value
of the loop variable j between its limits i + 1 and n - 1; this is repeated for each value
of the outer loop, i.e., for each value of the loop variable i between its limits 0 and n -
2.

 Example 3
o Given two n × n matrices A and B, find the time efficiency of the dentition-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:

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 16

Module-1

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.
 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 = AB
 for i ←0 to n - 1 do
 for j ←0 to n - 1 do
o C[i, j] ←0.0
o for k ←0 to n - 1 do
 C[i, j] ←C[i, j] + A[i, k] * B[k, j]
 return C
 Algorithm Analysis:
o An input‟s size of matrix order n.
o There are two arithmetical operations in the innermost loop (Multiplication and
Addition) in innermost loop each of the two is executed exactly once.
o Multiplication operation is considered as basic operation.
o Let us set up a sum for the total number of multiplications M(n) executed by the
algorithm.
o Since this count depends only on the size of the input matrices, we do not have to
investigate the worst-case, average-case, and best-case efficiencies separately.
o There is just one multiplication executed on each repetition of the algorithm‟s
innermost loop, which is governed by the variable k ranging from the lower bound 0
to the upper bound n - 1.
o Therefore, the number of multiplications made for every pair of specific values of
variables i and j is
n 1 n 1 n 1 n 1 n 1 n 1
M (n)  1   n   n 2  n3
i 0 j 0 k 0 i 0 j 0 i 0

o The total number of multiplications M(n) is expressed by the following triple sum:
n 1 n 1 n 1
M (n)  1
i 0 j 0 k 0

o We can compute this sum by using formula (S1) and rule (R1).
n 1
o Starting with the innermost sum 1 , which is equal to n, then
k 0
n 1 n 1 n 1 n 1 n 1 n 1
M (n)     n   n 2  n3
i 0 j 0 k 0 i 0 j 0 i 0

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 17

Module-1
o The running time of the algorithm on a particular machine m, we can do
T ( n )  Cm M ( n )  C m n 3
C
o Where m is the time of one multiplication on the machine, we would get a more
accurate estimate if we took into account the time spent on the additions, too:
T (n)  Cm M (n)  Ca A(n)  Cm n 3  Ca n3  (Cm  Ca )n 3
o Where Ca is the time of one addition.
 Example 4
o The following algorithm finds the number of binary digits in the binary
representation of a positive decimal integer.
 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
 Algorithm Analysis:
o An input‟s size is n.
o The loop variable takes on only a few values between its lower and upper limits.
o Since the value of n is about halved on each repetition of the loop, the answer should
be about log2n.
o The exact formula for the number of times the comparison n>1 will be executed is
actually └log2n┘+1.
2.4. Mathematical Analysis of Recursive Algorithms
 Recursion is technique used in computer science to solve big problems by breaking them into
smaller, similar problems.
 A function calls itself directly or indirectly is called recursion and the corresponding function
is called a recursive function.
2.4.1. 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 cans, 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.
 Example-1:
o Compute the factorial function F(n) = n!, for an arbitrary nonnegative integer n.
o Solution:

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 18

Module-1
 The factorial of some number can be obtained by performing repeated
multiplication.
 Example: let n=5 then
 Step 1: n! = 5!
 Step 2: 4!*5
 Step 3: 3!*4*5
 Step 4: 2!*3*4*5
 Step 5: 1!*2*3*4*5
 Step 5: 0!*1*2*3*4*5
 Step 6: 1*1*2*3*4*5 as 0! = 1.
 ALGORITHM F(n)
 //Computes n! recursively
 //Input: A nonnegative integer //Output: The value of n!
 if n = 0 return 1
 else return F(n- 1) * n
 Mathematical Analysis
 Step 1: The factorial algorithm works for input size n.
 Step 2: The basic operation in computing factorial is multiplication.
 Step 3: The recursive function call can be formulated as F(n) = F(n – 1)*n, where n > 0.
 Then the basic operation multiplications are given as M (n). and M(N) is multiplication
count to compute factorial (n)
M(n) = M(n – 1) + 1
To multiply factorial (n – 1) by n.

These multiplications are required

to compute factorial (n – 1)

 Step 4: In step 3 the recurrence relation is obtained. M(n) = M(n-1) + 1, now we will solve
recurrence using
 Forward substitution
 M(n) = M(n-1) + 1
o Let n = 1 then
 M(1) = M(1-1) + 1 =M(0) + 1 = 1
o Let n = 2 then
 M(2) = M(2-1) + 1 =M(1) + 1 = 1 + 1 = 2
o Let n = 3 then
 M(3) = M(3-1) + 1 =M(2) + 1 = 2 + 1 = 3 therefore M(n) = n
 Backward substitution
 M(n) = M(n-1) + 1 ----------- 1
o Let n = n - 1
 M(n - 1) = M(n – 1 – 1) + 1
 M(n – 1) = M(n – 2) + 1 ------ 2

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 19

Module-1
 Substitute 2 in 1 then M(n) = [M(n – 2) + 1] + 1 = M(n – 2) + 2 ------ 3
 M(n – 2) = M(n –2 – 1) + 1 = M(n – 3) + 1 ------ 4
 Substitute 4 in 3 then [M(n – 3) + 1] + 2 = M(n – 3) + 3
 From the substitution methods we can establish a general formula as

M (n – i) + i

Now let us prove correctness of this formula using mathematical induction as follows
Prove M(n) = n by using mathematical induction.
Basis: Let n = 0 then
M (n) = 0, i.e., M (n) = 0 = n
Induction: If we assume M (n - 1) = n – 1 then
M (n) = M (n – 1) + 1
=n–1+1
=n
i.e., M (n) = n
Thus the time complexity of factorial function is Θ (n)
 Example-1: Tower of Hanoi
o Solution:
 Tower of Hanoi is a example of recursive function.

 ALGORITHM TOH (n, A, B, C)

 {
o //If only one disk has to be moved
o if (n = 1) then
o {
 write (“The Peg moved from A to C”)
 return
o }
o else
o {
o //move top n-1 disks from A to B using C
o TOH(n – 1, A, B, C);
o //move remaining disks from B to C using A
o TOH(n – 1, B, C, A);
o }
 }

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 20

Module-1
 Mathematical Analysis:
Step 1: The input size n (total number of disks).
Step 2: The basic operation is moving disks from one peg to another. When n > 1, then to
move these disks from peg A to peg C using peg B, we first move recursively n – 1
disk from peg A to B using auxiliary peg C. Then, we move the largest disk directly
from peg A to peg C and finally move n – 1 disk from peg B to peg C (using peg
„A‟ as auxiliary peg). If n = 1 then we simply move the disk from peg A to peg C.
Step 3: The moves of disks are denoted by M(n). M(n) depends on number of disks n. The
recurrence relation can then set up as
M(1) = 1 therefore Only 1 move is needed TOH(1, ; ; ;)
If n > 1 then we need two recursive calls plus one move. Hence
M(n) = M(n – 1) + M(n – 1)

To move (n – 1) disks from peg A to B disk To move (n – 1) disks from peg B to C disk

To move largest disk from peg A to C disk

M(n) = 2M(n – 1) + 1 ------------ (1)

Step 4: Solving recurrence M(n) = 2M(n – 1) + 1 using two substitution methods.

 Forward Substitution:
For n > 1
 M(2) = 2M(1) + 1
o =2+1
 M(2) = 3
 M(3) = 2M(2) + 1
o = 2(3) + 1
 M(3) = 7
 M(4) = 2M(3) + 1
o = 2(7) + 1
 M(3) = 15
 Forward Substitution:
 M(n) = 2M(n – 1) + 1
 Put M(n – 1) = 2M(n – 2) + 1
 = 2[2M(n – 2) + 1] + 1
 = 4M(n – 2) + 2 + 1
 = 4M(n – 2) + 3 This is also written as 22 M(n – 2) + 2 + 1
 Put M(n – 2) = 2M(n – 3) + 1
 = 4[2M(n – 3) + 1] + 3

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 21

Module-1
 = 8M(n – 3) + 4 + 3
 = 8M(n – 3) + 7 Can be written as 23 M(n – 3) + 2 2 + 21 + 1
Above computations suggest us to compute next computation as
 = 24M(n – 4) + 23 + 22 + 2 + 1
From this we can establish a general formula as
 = 2iM(n – i) + 2i - 1 + 2i - 2 + …+ 2 + 1
 This can also be written as M(n) = 2iM(n – i) + 2i - 1-------------(2)
 Thus for obtaining M(n) we substitute n by n – I in the equation (2).
 Let us use mathematical induction to establish correctness of equation (2).
 Basis:
 As in equation (2) we can obtain M(n) by substituting n = n – I,
assume initially n = 1 then
 n–i=1
 i.e., i = n - 1
 i.e., M(n) = 2i M(n – i) + 2i – 1
 with i = n – 1 become
 M(n) = 2n - 1M(n – (n – 1)) + 2n – 1 – 1
 = 2n - 1M(n – n + 1)) + 2n – 1 – 1
= 2n – 1M(1) + 2n – 1 – 1
Put M(1) = 1
= 2n – 1 + 2n – 1 – 1
M(n) = 2n – 1
if n = 1, then 21 – 1 = 2 – 1 = 1 is proved.
 Induction :
 From equation (1) we get M(n) = 2M(n – 1) + 1 ------------(3)
 But in basis of induction we have computed M(n – 1) = 2n – 1 – 1
then substitute this value in equation (3) and will get
 M(n) = 2(2n – 1 – 1) – 1
 = 2n – 2 + 1
 M(n) = 2n - 1 is proved for n = n – 1
 We get recurrence as M(n) = 2n – 1
 From this we can conclude that tower of Hanoi has a time
complexity as Θ(2n – 1) = Θ(2n)
o The following algorithm finds the number of binary digits in the binary
representation of a positive decimal integer using recursion method.
 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

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 22

Module-1
 Recurrence Relation
Step 1: The input size n.
Step 2: The basic operation which is performed is division by 2.
Step 3: Now we will set up recurrence relation for this algorithm.
Let D(n) be a count of performing division to calculate
Binary_Rec(n)

2.5. Brute force approaches:

2.5.1. Selection Sort
 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
element 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.

 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
 if A[j ] <A[min] min ←j
o swap A[i] and A[min]
 Example

 Algorithm Analysis
Step 1: The input size is n.
Step 2: The basic operation is the key comparison A[j ] <A[min].
Step 3: The number of times it is executed depends only on the array size and is given
by the following sum:

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 23

Module-1

 Thus, selection sort is a Θ (n2) algorithm on all inputs.

[Link] Sort
 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:

 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
o for j ←0 to n - 2 - i do
 if A[j + 1] <A[j ]
 swap A[j ] and A[j + 1]
 Example

 Algorithm Analysis
Step 1: The input size is n.
Step 2: The basic operation is the key comparison A[j + 1] <A[j ]

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 24

Module-1
Step 3: The number of times it is executed depends only on the array size and is given
by the following sum:

Step 4: The number of key swaps, however, depends on the input. In the worst case of
decreasing arrays, it is the same as the number of key comparisons:

 Thus, bubble sort is a Θ (n2) algorithm on all inputs.

2.5.3. Sequential Search
 Algorithm Sequential-Search(A[0…n-1], k)
 {
 i := 0;
 while i < n and A[i] ≠ k do
 i := i + 1;
 if i < n then return i;
 else return -1;
 }
o Worst Case:

o Best Case:

o Average Case:

Cavg(n) = Probability of Successful + probability of unsuccessful

2.5.4. Brute-Force String Matching
The Brute Force algorithm compares the pattern to the text, one character at a time, until
unmatching characters are found.
Algorithm:
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

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S

 25

Module-1
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
Example:

 Compared characters are italicized.

 Correct matches are in boldface type.
 The algorithm can be designed to stop on either the first occurrence of the pattern, or upon
reaching the end of the text.
 Complexity:
o Given pattern M characters in length, and text N characters in length...
o Worst case: compares pattern to each substring of text of length M.
 For example, M=5.

Total number of comparisons: M (N-M+1).

Worst case time complexity: Ο (MN)

Analysis & Design of Algorithms (BCS401) Dr. Tamilarasan S