Module 1 – Introduction and Review

Introduction and Examples: What is an Algorithm? Algorithm Specification, Examples from real life: Air
Travel, Xerox Shop, Document Similarity and types of algorithms.
Motivation for Performance Analysis using Examples: Bubble Sort, Selection Sort, Insertion Sort, String
Pattern Matching. Contrast performance analysis versus actual runs.
Performance Analysis Framework: Space complexity, Time complexity. Asymptotic Notations: Big-Oh
notation (O), Omega notation (Ω), Theta not - recursive and recursive Algorithms with Examples.

Text Book 1: Chapter 1.1,2.1-2.4,3.1,3.2 Digital Resource: D1

1.1 WHAT IS AN ALGORITHM?

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.
This definition is illustrated by Fig. 1.1.

“Instructions” implies that there is something or someone capable of understanding and following the
instructions given.
“Computer,” - before the electronic computer was invented, the word “computer” meant a human
being involved in performing numeric calculations. Nowadays, “computers” are those ubiquitous
electronic devices that have become indispensable in almost everything we do.
Although the majority of algorithms are intended for eventual computer implementation, the notion
of algorithm does not depend on such an assumption.
To make a computer do anything, you have to write a computer program. To write a computer
program, you have to tell the computer, step by step, exactly what you want it to do. The computer
then "executes" the program, following each step mechanically, to accomplish the end goal. The
algorithm is the basic technique used to get the job done.

The notion of the algorithm illustrates some important points:

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 1

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

The characteristics of an algorithm are:

• Input: The range of inputs for which an algorithm works has to be specified carefully. Zero /
more quantities are externally supplied.
• Output: At least one quantity is produced.
• Definiteness: Each instruction / rule in the algorithm must be clear, well-defined and
unambiguous.
• Finiteness: If we trace out the instructions of an algorithm, then for all cases, the algorithm
should terminate after a finite number of steps.
• Efficiency: Every instruction must be very basic so that in principle, it can be carried out by a
person using only pencil and paper. It also must be feasible.
• The order of steps must be unambiguous.
• It should have a clear stopping point.

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

- Several algorithms for solving the same problem may exist.
- Algorithms for the same problem can be based on very different ideas and can solve the problem
with different speeds.
- Each algorithm has advantages and disadvantages in different situations. Depending on the task
at hand, the best one is chosen.

1.1.1 Example 1: Euclid’s algorithm

Euclid’s algorithm solves the problem of finding the greatest common divisor (gcd) of two
nonnegative numbers, not both zero. The gcd of m and n, written as gcd(m, n), is the largest integer
that divides both evenly i.e. with a remainder of zero.
Euclid of Alexandria (third century B.C.) proved that
gcd(m, n), where m>n>0, equals gcd(n, m mod n),
where m mod n is the remainder of the division of m by n.

Example: Compute gcd(60, 24).

gcd(60, 24) = gcd(24, 60 mod 24)
= gcd(24, 12)
= gcd(12, 24 mod 12)

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 2

 = gcd(12, 0) = 12.

1.1.2 Structured Description of Eucid’s Algorithm

Euclid’s algorithm for computing gcd(m, n)
Step 1 If n = 0, return the value of m as the answer and stop; otherwise, proceed to Step 2.
Step 2 Divide m by n and assign the value of the remainder to r.
Step 3 Assign the value of n to m and the value of r to n. Go to Step 1.

1.1.3 Pseudocode of Eucid’s Algorithm

ALGORITHM Euclid(m, n)
//Computes gcd(m, n) by Euclid’s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n ≠ 0 do
r ←m mod n
m←n
n←r
return m

1.1.4 How do we know that Euclid’s algorithm eventually comes to a stop?

The second integer of the pair gets smaller with each iteration and it cannot become negative.
The new value of n on the next iteration is m mod n, which is always smaller than n.
Hence, the value of the second integer eventually becomes 0, and the algorithm stops.

1.1.5 Consecutive integer checking algorithm for computing gcd(m, n)

This is simply based on the definition of the greatest common divisor of m and n as the largest integer
that divides both numbers evenly. Obviously, such a common divisor cannot be greater than the smaller
of these numbers.
Let t = min{m, n}.
We can start by checking whether t divides both m and n:
if it does, t is the answer;
if it does not, we simply decrease t by 1 and try again.
(How do we know that the process will eventually stop?)
For example, for numbers 60 and 24, the algorithm will try first 24, then 23, and so on, until it reaches
12, where it stops.

1.1.6 Consecutive integer checking algorithm for computing gcd(m, n)

Step 1 Assign the value of min{m, n} to t.
Step 2 Divide m by t. If the remainder of this division is 0, go to Step 3;
otherwise, go to Step 4.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 3

 Step 3 Divide n 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.
Step 4 Decrease the value of t by 1. Go to Step 2.

The consecutive integer checking algorithm, in the form presented, does not work correctly when
one of its input numbers is zero. This example illustrates why it is so important to specify the set of
an algorithm’s inputs explicitly and carefully.

1.1.7 Middle-school procedure for computing gcd(m, n)

Step 1 Find the prime factors of m.
Step 2 Find the prime factors of n.
Step 3 Identify all the common factors in the two prime expansions found in Step 1 and Step 2.
(If p is a common factor occurring pm and pn times in m and n, respectively, it should be
repeated min{pm, pn} times.)
Step 4 Compute the product of all the common factors and return it as the greatest common divisor
of the numbers given.
Thus, for the numbers 60 and 24, we get
60 = 2 . 2 . 3 . 5
24 = 2 . 2 . 2 . 3
gcd(60, 24) = 2 . 2 . 3 = 12.
Note that this procedure is much more complex and slower than Euclid’s algorithm.
In addition to inferior efficiency, the middle school procedure does not qualify, in the form presented, as a
legitimate algorithm; because the prime factorization steps are not defined unambiguously: they require a
list of prime numbers.
Step 3 is also not defined clearly enough.

1.1.8 Sieve of Eratosthenes

This is a simple algorithm for generating consecutive primes not exceeding any given integer n > 1. It was
probably invented in ancient Greece and is known as the sieve of Eratosthenes (ca. 200 b.c.).
Generates consecutive primes not exceeding any given integer n > 1 by the sieve of Eratosthenes.
Step 1: List consecutive integers from 2 to n.
Step 2: Eliminate from the list all multiples of 2, i.e., 4, 6, and so on.
Step 3: Move to the next item on the list, and eliminate its multiples.
Note: No pass for number 4 is needed: since 4 itself and all its multiples are also multiples of 2, they
were already eliminated on a previous pass.
Step 4: Repeat Step 3 until no more numbers can be eliminated from the list.
Step 5: The remaining integers of the list are the primes needed.

1.1.9 Sieve of Eratosthenes – Example

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 4

Find the list of primes not exceeding n = 25:

The consecutive primes less than or equal to 25 are:

2, 3, 5, 7, 11, 13, 17, 19, 23.

What is the largest number p whose multiples can still remain on the list to make further iterations of the
algorithm necessary? - If p is a number whose multiples are being eliminated on the current pass, then the
first multiple we should consider is p . p because all its smaller multiples 2p, . . . , (p − 1)p have been
eliminated on earlier passes through the list. This observation helps to avoid eliminating the same number
more than once.
Also, p . p should not be greater than n, and therefore p cannot exceed √n rounded down (denoted ⌊√n⌋ ).

1.1.10 Sieve of Eratosthenes - Algorithm

ALGORITHM Sieve(n)
//Implements the sieve of Eratosthenes
//Input: A positive integer n > 1
//Output: Array L of all prime numbers less than or equal to n
for p←2 to n do A[p]←p
for p←2 to ⌊√n⌋ do
if A[p] ≠ 0 //p hasn’t been eliminated on previous passes
j←p∗p
while j ≤ n do
A[j ]←0 //mark element as eliminated
j ←j + p
//copy the remaining elements of A to array L of the primes
i ←0
for p←2 to n do
if A[p] ≠ 0
L[i]←A[p]
i ←i + 1
return L

1.2 Algorithm Specification

1.2.1 Difference between an algorithm and a program
An algorithm terminates after a finite number of steps. A program does not have to satisfy this finiteness
condition. For example, an operating system continues in a “wait" loop until more jobs are entered. Such a

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 5

program does not terminate unless the system crashes.

1.2.2 Methods of Specifying an Algorithm

There are three ways to specify an algorithm. They are:
a. Natural Language
b. Flowchart
c. Pseudocode
a. Natural Language
It is very simple and easy to specify an algorithm using a natural language like English. If we use this option,
we should make sure that the resulting instructions are definite.
But, many times the specification of algorithm by using natural language is not clear.
Example: An algorithm to perform addition of two numbers.
Step 1: Read the first number, say a.
Step 2: Read the second number, say b.
Step 3: Add the above two numbers and store the result in c.
Step 4: Display the result from c.

b. Flowchart
Flowchart is a graphic representation of an algorithm. It specifies an algorithm by a collection of connected
geometric shapes containing descriptions of the algorithm’s steps. But, flowcharts work well only if the
algorithm is small and simple.
Example: An algorithm to perform addition of two numbers.

Fig. 1.2 Flowchart to add two numbers

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 6

c. Pseudocode
Pseudocode is a combination of natural language and programming language constructs. Pseudocode is
usually more precise than natural language.
Example: An algorithm to perform addition of two numbers.

1.3 Examples from Real Life: Air Travel

https://www.youtube.com/watch?v=55Ivl9pu_0U&t=3s
Let us consider an airline - Barbet airlines, which serves several cities in the country. Although it serves
several cities, it does not really connect all these cities directly. Only some of the cities are connected by
direct flights. For other pair of cities you have to take a hopping flight i.e. you have to go via an intermediate
city. There could be several goals in this problem.

1.3.1 Goals
Goal 1: Compute every pair of cities, which are actually connected by this network served by this airline.
How do we compute all pairs of cities A, B such that A and B are connected by a sequence of flights?
Goal 2: Is it really possible go from say Varanasi to Trivandrum or is it not possible?
Goal 3: How do we go from A to B?

1.3.2 Methodology

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 7

 Fig. 1.3 Barbet airlines – route map
For this, first we need to look at the network, an example of a route map is shown in Fig. 1.3. This is a
physical map of the country with the cities marked out. There are about ten cities - Delhi, Varanasi,
Ahmedabad, down to Trivandrum in the south with some arrows indicating the flights. Some of these flights
are in one direction. For example, you can go from Delhi to Varanasi, but you cannot come back directly to
Delhi; you must go to Ahmedabad and then come back.
Some routes could be triangular routes, where you go around a triangle i.e. you cannot go back directly
without hopping in between.
Some pairs of important cities, like Mumbai and Delhi, might be connected by flights in both directions.
Similarly even Mumbai and Calcutta.
To answer all the above questions, our first step is to model this problem in such a way that we retain the
essential details, which are relevant to solving the problem and do away with the unnecessary details.
Actually, we only need the structure of this network; the map itself is not relevant. We just need to know
how many cities are on the network and how they are connected by the flights. In this diagram, the cities
are the gray circles and the flights are the arrows and the arrow heads indicates the direction. If the arrow
head is in one end only, it is a one directional flight; if there is an arrow head in both ends, it is a bidirectional
flight. This structure can be shown by the diagram in Fig. 1.4. This kind of a picture is called graph. A
graph consists of nodes and edges.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 8

 Fig. 1.4 Barbet airlines – Graph Representation
1.3.3 Connected Destinations
We need to compute a path. For this, we need the connected destinations.
A path is the sequence of edges going from one city to another city; where the direction must be correct.
You cannot go backwards, across an edge which is flying from A to B; you cannot take this flight B to A,
unless there is another flight.
Next, how do we take this picture and put it into a form that we can manipulate using a program or an
algorithm. For this, we need a suitable data structure in order to represent this graph. Then, we need to
manipulate it to answer the question that we handle, in this case, connectivity. How do we go from A to B
or can we go from A to B or which all cities B can I reach from A?

1.3.4 Efficiency
Next, how do we design such an algorithm, given the way we have represented these cities in the graph?
Does it depend on the representation? There could be multiple representations, some of which gives us more
or less efficient algorithm.
These are all the questions that we need to answer before we can decide on whether we have got the best
solution or not.
In terms of efficiency, we have to look at what are the things that determine the complexity of a problem.
1) It is fairly obvious that if we have more cities, the problem is more complicated. So, the number of cities,
say N, is parameter which determines how complicated the algorithm is going to be, or rather how long
it is going to take to run.
2) The other parameter which determines how complex the network is, is the number of direct flights, say

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 9

 F. Obviously, if there are fewer flights, there are fewer places, which can be connected and we have to
explore fewer possibilities.
So from this, it follows that computing the paths depends on both N and F.
3) We will not have an algorithm which will always take a constant number of steps, say twenty steps. It
will be some number of steps depending on N and F. What is this dependency? How does it grow?
If N grows by a factor of ten, does it takes ten times more or hundred times more time?
4) What realistic size of networks can we handle? How large a value of N and F can be handled?
If the airline grows to twenty flights, we will still have be able to give our answer in the reasonable time.
Online booking requires response in seconds. It is not enough to come back after an hour and say “yes,
there is a flight from Trivandrum to Calcutta”.
5) What is the limit of our efficiency? Can we scale this algorithm to cover airlines, multiple airlines?
Then, we can have a website which actually allows booking across all airlines i.e. one can go from place
A to place B. This depends on how larger value of N and F we can handle.

1.3.5 Variations
The problem discussed so far is a very simple problem; can I travel from A to B? But very often, you want
to go from A to B within some reasonable time frame.
Flights have arrival and departure times. It is not usually acceptable to break journey overnight. At the
same time, you also do not want to spend more than a certain amount of time (say four hours) in between
flights. Though there may be many connections, only some connections are feasible.
The problem becomes little more constraint. So, we do not just want to look at the connected paths from A
to B. But look at connected paths A to B, which meet some additional constraints in terms of timing and
other things.
How do we compute feasible paths with constraints? Can we solve this problem with the same approach
that we solve the simple problem or we need to take a radically different approach or do we need more
information in order to decide or solve the problem.

1.3.6 Other Problems

1.3.6.1 Cost
Each sector has a cost. As a passenger, the cost would be the price of ticket. If you are trying to compute
the best way to go from A to B, your motivation might be to choose the cheapest route in terms of the
ticket cost.
But, cost is not only money; cost could be time as well. You might also want the fastest route from A to B,
the one which involves the least waiting.
So, it depends on what your priority is. If you are in a hurry to reach a destination, you do not mind paying
more. However, when going on a vacation with family, you have a relax time schedule, but you want to
make sure you get a value from money.

1.3.6.2 Maintenance

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 10

From the airlines point of view there may be other concerns. Periodically, an aircraft have to be brought
down for a day for maintenance. One does not want to have many aircrafts to keep all the routes flying and
wastefully keep planes unused at other times.
On the other hand, if one keeps too few planes, then when an aircraft is brought down for maintenance,
some routes have to be sacrificed. Which routes should be sacrificed, such that the connectivity of the
network remains the same? That is, if you could go earlier from Trivandrum to Calcutta, during a
maintenance shutdown also you should still be able to go from Trivandrum to Calcutta maybe by different
route.
Thus, there are very many different points of view based on which you can query this basic air network that
has been described using a graph.

1.4 Examples from Real Life: Xerox Shop

https://www.youtube.com/watch?v=9yVJCCNFDUI
Suppose there is a xerox (photo copy) shop, Campus Xerox, inside the university campus.
The deadline for projects is approaching and a bunch of students want their project reports printed urgently.
They go and submit their reports to the xerox shop, and say that they want so many copies made within
such a time. The number of pages for each job is known. Also, each customer has been promised delivery
by a deadline.
1.4.1 Goal
How to schedule the pending jobs most effectively?
There are many different ways in which this problem can be phrased. Let us look at one of them.
Suppose the students have submitted their jobs and this shop, Campus Xerox, is competing against some
rivals. So, it is offering a special deal - say it gives each customer a promised delivery time and if does not
meet the schedule, it will give a discount.
Some of these jobs are big and some are small i.e. some printing jobs will be finished faster while some will
take longer, but they all have to run on the same machines that is available in the Xerox shop at the same
time. These jobs can be reordered i.e. some job that has come later can be put earlier on the machine and
hope to finish it within its deadline, so that discount need not be given on this job. You can take something
which is going to take longer and postpone it saying, anyway it is not going to meet the deadline and give
up the discount on that job.
So, the job / problem for the Xerox shop is how to do this schedule. This can be done by various
mechanisms.

1.4.2 Different approaches

One is the brute force approach. Since the printing jobs are to be allocated in some order, try every possible
order and choose the one which gives me the best return. The problem with this is that it will take a very
large amount of time to do this, as the number of possibilities is exponential. Even if you have just 30
requests pending, it could take several hours to find an optimized schedule, and several hours might have
gone ahead during which some work is done. In this case, some jobs were done perhaps not optimally, yet

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 11

at least some money was got for them.

Next, is to decompose the problem and solve this problem by reducing it to a simpler problem. First,
choose a job optimally to schedule and the machine on which it will run, according to some strategy. That
is, pick each job as the first job, determine how much time it takes to complete and then select the most
efficient one. Then, recursively solve the problem for the remaining N-1 jobs.
Another option is the greedy approach. Look at all the jobs which are yet to be done, find some criteria by
which we choose the next job to do without looking at all the possibilities of doing the other jobs and
complete it. The choice of the next job is done once and for all; never go back and try another job sequence.
We have to justify that the chosen criteria is actually optimal. But, it is not sure if this strategy always gets
the best possible return.
There are different criteria to choose the next job. It could be the least number of pages that is the shortest
time to print, or the job closest to the deadline that is the one which we are most likely to miss finishing in
time and having to give a discount, etc.

1.4.3 Variations
There could be different variations to this basic problem.
- If we assume that the shop has many photo copiers, it is reasonable to assume that some are new and
some are old. The new ones may work faster than the ones are that are old. Therefore, the time that will
take to finish a job depends on which machine the job is put on.
- If competition among the xerox shops is considered, the strategies / rewards chosen for all types of
machines may not be uniform over all the machines.
- When we use a machine; we use some other resources as well – like ink, paper, electricity, etc. and
this cost may vary from one machine to another.
If a job is split machines, the cost for the shop might be only in terms of time; the cost for the shop
maybe more or less. So, the actual revenue that the shop realizes maybe more or less depending on
which machine it chooses.
- A machine cannot run indefinitely without having to be stopped for some time for maybe maintenance,
for loading paper, for setting up between jobs, etc. We cannot realistically assume that every machine
is continuously available.
Thus, there is a basic problem with some constraints which you want to solve, but that problem can be made
more realistic by adding several new features. By the time you add a new feature, you have to see whether
the solution that you have for the simpler problems still works or the new feature demands radically new
approach and if so how you should get that.

1.5 Examples from Real Life: Document Similarity

https://www.youtube.com/watch?v=mYh2MaOusCk&t=2s
Suppose we have two documents and our goal is to find out how similar they are. These two documents can
be really variations of the same document. There are many different scenarios where this problem is
interesting.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 12

1.5.1 Applications of Document Similarity
- Plagiarism detection
- Checking changes between versions of code
- Answering web search queries more effectively.

1.5.1.1 Plagiarism detection: Suppose somebody has put an article in a newspaper or on a website and you
believe that this author has not really written the article themselves. Probably, they have copied these articles
from somewhere else. If you are a teacher in a course, you might be worried that two students have submitted
the same assignments or one student has copied an assignment some details from some source. If you can
measure how similar two documents are, you can try to quantify this notion that somebody has copied from
somebody else.

1.5.1.2 Checking changes between versions of code: It might also be used when some people are writing
code typically writing programs for some application. Over a period of time, documents evolve as the
programs evolve. They might add some features. You might want to look at two different pieces of code
and try to figure out what changes have taken place - how similar they are or how different they are.
1.5.1.3 Answering web search queries more effectively: If you query a search engine and it reports results,
typically it tries to group together results which is similar. Suppose. there are 10 different copies or similar
copies of a document saying more or less the same thing and these show up as your first 10 search results.
Say, there exists another document that is highly relevant and quite different from these; this document will
be lost because it will not be in the first page of searches. Hence, it is useful to be able to group together the
results of a search query by similarity, so that the user is actually presented by an effective choice between
different answers to the search query and not just the large number of variations of the same answers.

1.5.2 Measure of Similarity

If our motivation is to compare documents, what is a good measure of similarity of documents? There are
many different notions that people have come up with. Obviously, it has to do something with the order
towards and the choice of letters. One way of quantifying the distance in a document is to use the edit
distance.
Edit distance is a measure of how many changes you have to make to transform one document into another
document. The operations you can do are limited, so that we have a uniform way of counting. For example,
we could say that edit involves how many characters are being changed. Now, each step of editing i.e. one
change will either add or remove a letter and perhaps replace one letter by another letter. We can now count
these basic steps - adding or removing the letter or replacing one letter by another, and find out how many
steps it takes to edit one document to make it to another document.
Thus, edit distance is the minimum number of edit operations to transform one document to another.

1.5.3 How do we compute edit distance?

The question is how do you decide what is the best way to edit one document and make it another document.
The trivial solution is to block cut and block paste. You can just delete all the letters and then type in the
new documents.

1.5.3.1 Brute force approach

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 13

You can try out all possible delete and insert sequences and see which among them gives you the best
solution. But this is very inefficient kind of solution and is not likely to be the best possibility.

1.5.3.2 Decomposing the problem

Suppose our first goal is just to make the first character of the two documents the same. Let us explore all
possible edit operations that make this possible.
If the first character in the two documents are already the same, we leave and go on. If they are not the same,
we have two options:
- We can either transform the first character to be equal or
- We can insert a character in one of the two documents.
Suppose the first document starts with an x and the second document with a z. To reach our goal, either we
can change x into z or z into x or we can insert x before the z in the second document or z before the x in
the first document. Once we have done this, we have made the first character the same; then we can
recursively try to fix the rest of the document.
One of the difficulties we face when we do recursion in this manner is that the same sub-problem comes up
for solutions many times. Thus, naïve recursion is inefficient.
We can get around this problem using dynamic programming.
In dynamic programming, we do not compute the same sub-problems twice. Whenever we solve a sub-
problem, we store it somewhere, look it up and make sure that you do not do it again.
1.5.4 Variations
This problem of, the difference or similarity between two documents can be looked at many different levels.
• Focus on words, the actual text (as done in 1.5.3.2).
• Interested only in the meaning of the document.
• Documents are near if they overlap on many words
- Order in which words occur may not matter
- Useful for topic based web search
- Can have dictionary of “similar” words.

1.6 Types of Algorithms

There are many types of algorithms, including brute force, greedy, dynamic programming, divide and
conquer, backtracking, decision trees, and machine learning algorithms.
1.6.1 Brute Force Algorithm or Exhaustive Search Algorithm
This is the most basic and simplest type of algorithm.
Brute force is a straightforward approach to solving a problem, usually directly based on the problem
statement and definitions of the concepts involved.
More technically it is just like iterating every possibility available to solve that problem.
Example: If there is a lock of 4-digit PIN. The digits to be chosen from 0-9 then the brute force will be

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 14

trying all possible combinations one by one like 0001, 0002, 0003, 0004, and so on until we get the right
PIN. In the worst case, it will take 10,000 tries to find the right combination.

1.6.2 Recursive Algorithm

This type of algorithm is based on recursion. In recursion, a problem is solved by breaking it into
subproblems of the same type and calling itself again and again until the problem is solved with the help of
a base condition. Some common problems that are solved using recursive algorithms are Factorial of a
Number, Fibonacci Series, Tower of Hanoi, DFS for Graph, etc.

1.6.3 Divide and Conquer Algorithm

Divide-and-conquer is probably the best-known general algorithm design technique. Divide-and-conquer
algorithms work according to the following general plan:
1. A problem's instance is divided into several smaller instances of the same problem, ideally of about the
same size.
2. The smaller instances are solved (typically recursively, though sometimes a different algorithm is
employed when instances become small enough).
3. If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original
instance.
The divide-and-conquer technique is shown Fig. 1.5.

Fig. 1.5 Divide-and-conquer technique (typical case).

Some common problems that are solved using Divide and Conquer Algorithm are Merge Sort, Quick

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 15

Sort, Strassen’s Matrix Multiplication, etc.

1.6.4 Decrease and Conquer

Decrease and conquer is a technique used to solve problems by reducing the size of the input data at each
step of the solution process. This technique is similar to divide-and-conquer, in that it breaks down a
problem into smaller subproblems, but the difference is that in decrease-and-conquer, the size of the input
data is reduced at each step. The technique is used when it’s easier to solve a smaller version of the problem,
and the solution to the smaller problem can be used to find the solution to the original problem.
Some examples of problems that can be solved using the decrease-and-conquer technique include binary
search, finding the maximum or minimum element in an array, and finding the closest pair of points in a set
of points.

1.6.5 Transform and Conquer

Transform-and-conquer methods work as two-stage procedures. First, in the transformation stage, the
problem’s instance is modified to be, for one reason or another, more amenable to solution. Then, in the
second or conquering stage, it is solved.
There are three major variations of this idea that differ by what we transform a given instance (Fig. 1.6):
- Transformation to a simpler or more convenient instance of the same problem - instance simplification.
- Transformation to a different representation of the same instance - representation change.
- Transformation to an instance of a different problem for which an algorithm is already available -
problem reduction.

Fig. 1.6 Transform-and-conquer strategy.

Use cases: Data compression, machine learning, Image processing.

1.6.6 Dynamic Programming Algorithm

Dynamic programming is a technique for solving problems with overlapping subproblems. Typically, these
subproblems arise from a recurrence relating a given problem’s solution to solutions of its smaller
subproblems. Rather than solving overlapping subproblems again and again, dynamic programming
suggests solving each of the smaller subproblems only once and recording the results in a table from which
a solution to the original problem can then be obtained.
This technique can be illustrated by the Fibonacci numbers. The Fibonacci numbers are the elements of the
sequence
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . ,
which can be defined by the simple recurrence
F(n) = F(n − 1) + F(n − 2) for n > 1 ……………… (1.1)
and two initial conditions

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 16

 F(0) = 0, F(1) = 1. ……………….. (1.2)
If we try to use recurrence (1.1) directly to compute the nth Fibonacci number F(n), we would have to
recompute the same values of this function many times. Fig. 1.7 shows an example.

Fig. 1.7 Tree of recursive calls for computing the 5th Fibonacci number by the recursive definition
The problem of computing F(n) is expressed in terms of its smaller and overlapping subproblems of
computing F(n − 1) and F(n − 2). So, we can simply assign elements of a one-dimensional array with the n
+ 1 consecutive values of F(n) by starting, in view of initial conditions (1.2), with 0 and 1 and using equation
(1.1) as the rule for producing all the other elements. Obviously, the last element of this array will contain
F(n).
The problems that can be solved using the Dynamic Programming algorithm are Knapsack
Problem, Weighted Job Scheduling, Floyd Warshall Algorithm, etc.

1.6.7 Greedy Algorithm

The greedy approach suggests constructing a solution through a sequence of steps, each expanding a
partially constructed solution obtained so far, until a complete solution to the problem is reached. On each
step the choice made must be:
- feasible i.e., it has to satisfy the problem’s constraints,
- locally optimal i.e., it has to be the best local choice among all feasible choices available on that step,
- irrevocable i.e., once made, it cannot be changed on subsequent steps of the algorithm.
Some common problems that can be solved through the Greedy Algorithm are Dijkstra Shortest Path
Algorithm, Prim’s Algorithm, Kruskal’s Algorithm, Huffman Coding, etc.

1.6.8 Backtracking Algorithm

In Backtracking Algorithm, the problem is solved in an incremental way i.e. it is an algorithmic technique
for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing
those solutions that fail to satisfy the constraints of the problem at any point of time.
Some common problems that can be solved through the Backtracking Algorithm are the Hamiltonian
Cycle, M-Coloring Problem, N Queen Problem, Rat in Maze Problem, etc.

1.7 Performance Analysis Framework

There are two kinds of efficiency:
- time efficiency, also called time complexity, indicates how fast an algorithm in question runs.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 17

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

1.7.1 Measuring an Input’s Size

- Almost all algorithms run longer on larger inputs. For example, it takes longer to sort larger arrays,
multiply larger matrices, and so on. Therefore, it is logical to investigate an algorithm’s efficiency as a
function of some parameter n indicating the algorithm’s input size.
In most cases, selecting such a parameter is quite straightforward. For example, it will be the size of the
list for problems of sorting, searching, finding the list’s smallest element, and most other problems
dealing with lists.
- For the problem of evaluating a polynomial p(x) = anxn + . . . + a0 of degree n, it will be the
polynomial’s degree or the number of its coefficients, which is larger by 1 than its degree. Such a
minor difference is inconsequential for the efficiency analysis.
- The choice of a parameter indicating an input size matters in some situations. For example, to
compute the product of two n × n matrices, the matrix order n is essential.
- The choice of an appropriate size metric can be influenced by operations of the algorithm in question.
For example, how should we measure an input’s size for a spell-checking algorithm? If the algorithm
examines individual characters of its input, we should measure the size by the number of characters; if it
works by processing words, we should count their number in the input.
- To measure the input size for algorithms solving problems such as checking primality of a positive
integer n, the input is just one number, and it is this number’s magnitude that determines the input size.
In such situations, it is preferable to measure size by the number b of bits in the n’s binary representation:
b = ⌊ log2n ⌋ + 1.

1.7.2 Units for Measuring Running Time

To measure an algorithm’s running time, we can use some standard unit of time measurement - a second,
millisecond, etc.
But, some drawbacks to such an approach are:
- dependence on the speed of a particular computer,
- dependence on the quality of a program implementing the algorithm,
- dependence on the quality of the compiler used in generating the machine code, and
- the difficulty of clocking the actual running time of the program.
Since we are measuring an algorithm’s efficiency, we would like to have a metric 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.
First, identify the most important operation of the algorithm, called the basic operation. The operation
contributing the most to the total running time is the basic operation.
Then, compute the number of times the basic operation is executed.
It is not difficult to identify the basic operation of an algorithm: it is usually the most time-consuming
operation in the algorithm’s innermost loop.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 18

For example, most sorting algorithms work by comparing elements (keys) of a list being sorted with each
other; for such algorithms, the basic operation is a key comparison.
The running time (T(n) ) of an algorithm is calculated as
T(n) ≈ cop C(n)
where
n is the input size,
cop = Execution time of an algorithm’s basic operation on a particular computer,
C(n) = Number of times this operation needs to be executed.
Example:
Algorithm:Maxelement(A[0….n-1]
//Program description: Finding max number in array
//Input: An array element
//Output : return max number
{
max=A[0];
for i=1 to n do
if (A[i]>max)
max=A[i];
end for
return max
}
The running time is T(n) ≈ cop C(n)
≈ cop n
Here is an important application.
Let cop be the execution time of an algorithm’s basic operation on a particular computer, and
let C(n) be the number of times this operation needs to be executed for this algorithm.
Then we can estimate the running time T(n) of a program implementing this algorithm on that computer
by the formula
T(n) ≈ cop C(n).
Of course, this formula should be used with caution. The count C(n) does not contain any information about
operations that are not basic, and, in fact, the count itself is often computed only approximately.
Further, the constant cop is also an approximation whose reliability is not always easy to assess.
Still, unless n is extremely large or very small, the formula can give a reasonable estimate of the
algorithm’s running time.
It also makes it possible to answer such questions as “How much faster would this algorithm run on a
machine that is 10 times faster than the one we have?” The answer is, obviously, 10 times.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 19

Or, assuming that C(n) = ½ n(n − 1), how much longer will the algorithm run if we double its input size?
The answer is about four times longer.
Indeed, for all but very small values of n,

Therefore,

Note that we were able to find the complexity without actually knowing the value of cop: it was neatly
cancelled out in the ratio. Also note that ½, the multiplicative constant in the formula for the count C(n),
was also cancelled out.
The efficiency analysis framework ignores multiplicative constants and concentrates on the count’s order
of growth to within a constant multiple for large-size inputs.

1.7.3 Orders of Growth

Order of growth in algorithm means how the time for computation increases when you increase the
input size. The behavior of an algorithm changes with the input size. For large values of n, it is the function’s
order of growth that counts. Table 1.1 contains values of a few functions that are important for the analysis
of algorithms.
Table 1.1 Values (some approximate) of several functions important for analysis of algorithms

Order of growth of the above functions (Lower to higher order) is

1 < log n< n < n log n < n2 < n3< 2n < n!
The function growing the slowest among these is the logarithmic function.
Consider how the order of growth of the functions react to changes in input size, say, a twofold increase in
the value of their argument n.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 20

The function log2n increases in value by just 1 (because log22n = log22 + log2n = 1 + log2n);
the linear function increases twofold,
the linearithmic function n log2n increases slightly more than twofold;
the quadratic function n2 and cubic function n3 increase fourfold and eightfold.

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

An algorithm's efficiency is a function of a parameter indicating the size of the algorithm's input.
However, there are many algorithms for which running time depends not only on an input size but also on
the specifics of a particular input.
Consider, as an example, sequential search.
Here is the algorithm’s pseudocode, in which, for simplicity, a list is implemented as an array. It also
assumes that the second condition A[i] ≠ K will not be checked if the first one, which checks that the array’s
index does not exceed its upper bound, fails.

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

- The running time of this algorithm can be quite different for the same list size n.
- In the worst case, when there are no matching elements or the first matching element happens to be the
last one on the list, the algorithm makes the largest number of key comparisons among all possible inputs
of size n: Cworst(n) = n.

1.8.1 Worst-case Efficiency

The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n, which is an
input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size.
The way to determine the worst-case efficiency of an algorithm is, in principle, quite straightforward:
- analyze the algorithm to see what kind of inputs yield the largest value of the basic operation’s count
C(n) among all possible inputs of size n and then
- compute this worst-case value Cworst(n).
Clearly, the worst-case analysis provides very important information about an algorithm’s efficiency by
bounding its running time from above.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 21

1.8.2 Best-case Efficiency
The best-case efficiency of an algorithm is its efficiency for the best-case input of size n, which is an input
(or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that size.
The best-case efficiency can be analysed as follows:
- Determine the kind of inputs for which the count C(n) will be the smallest among all possible inputs of
size n. (Note that the best case does not mean the smallest input; it means the input of size n for which
the algorithm runs the fastest.)
- Ascertain the value of C(n) on these most convenient inputs.
For example, the best-case inputs for sequential search are lists of size n with their first element equal to a
search key; accordingly, Cbest(n) = 1 for this algorithm.

1.8.3 Average-case efficiency

Average case analysis of an algorithm seeks to determine its expected performance over all possible inputs.
Neither the worst-case analysis nor its best-case analysis yields the necessary information about an
algorithm’s behavior on a “typical” or “random” input. This is the information that the average-case
efficiency seeks to provide.
To analyze the algorithm’s average-case efficiency, we must make some assumptions about possible inputs
of size n.
Consider again sequential search. The standard assumptions are that
(a) the probability of a successful search is equal to p (0 ≤ p ≤ 1) and
(b) the probability of the first match occurring in the ith position of the list is the same for every i.
Under these assumptions,we can find the average number of key comparisons Cavg(n) as follows.
In the case of a successful search,
- the probability of the first match occurring in the ith position of the list is p/n for every i, and
- the number of comparisons made by the algorithm in such a situation is obviously i.
In the case of an unsuccessful search, the number of comparisons will be n with the probability of such a
search being (1− p). Therefore,

This general formula yields some quite reasonable answers. For example,
- If p = 1 (i.e., the search must be successful), the average number of key comparisons made by sequential
search is (n + 1) /2; i.e., the algorithm will inspect, on average, about half of the list's elements.
- If p = 0 (i.e., the search must be unsuccessful), the average number of key comparisons will be n because

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 22

 the algorithm will inspect all n elements on all such inputs.

Investigation of the average-case efficiency is considerably more difficult than investigation of the worst-
case and best-case efficiencies. Hence, for simplicity, the average-case efficiency of algorithms under
discussion are mostly quoted.
There are many important algorithms for which the average-case efficiency is much better than the worst-
case efficiency.

1.8.4 Amortized efficiency

Amortized efficiency applies not to a single run of an algorithm but rather to a sequence of operations
performed on the same data structure.
It turns out that in some situations a single operation can be expensive, but the total time for an entire
sequence of n such operations is always significantly better than the worst-case efficiency of that single
operation multiplied by n. So we can “amortize” the high cost of such a worst-case occurrence over the
entire sequence.

1.9 Recapitulation of the Analysis Framework

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

1.10 Asymptotic Notations and Basic Efficiency Classes

The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation
count as the principal indicator of the algorithm’s efficiency. To compare and rank such orders of growth,
computer scientists use three notations:
- O (big oh),
- Ω (big omega), and
- Θ (big theta).
1.10.1 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 n0 such that t(n) ≤ cg(n) for all n ≥ n0.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 23

The definition is illustrated in Fig. 1.8.

Fig. 1.8 Big-oh notation: t(n) ∈ O(g(n)).

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).
For example, the following assertions are all true:

P1. Prove the assertion: 100n + 5 ∈ O(n2).

Let g(n) = n2 and t(n) = 100n + 5.
100n + 5 ≤ 100n + n (for all n ≥ 5) = 101n ≤ 101n2 (for all n ≥ 2).
Thus, constant c = 101 and n0 = 5.
P2. Show that 100n + 5 ∈ O(n).
Let g(n) = n and t(n) = 100n + 5.
100n + 5 ≤ 100n + n (for all n ≥ 5) = 101n ≤ 101n.

P3. Show that 100n2 + 5n + 2 ∈ O(n2).

According to Big O definition, a function t(n) ∈ O(g(n)) iff c and n0 are found such that t(n) ≤ cg(n) for all
n ≥ n0.
Here, t(n) = 100n2 + 5n + 2
g(n) = n2
Let us assume that c = 101
n0 t(n) = 100n2 + 5n + 2 c g(n) = 101 n2 t(n) ≤ cg(n)
0 2 0 false
1 107 101 false
2 412 404 false
3 917 909 false
4 1622 1616 false

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 24

 5 2527 2525 false
6 3632 3636 true
7 4937 4949 true
Thus, we see that t(n) ≤ cg(n) for all n ≥ 6 i.e. n0 and c = 101. Hence proved that 100n2 + 5n + 2 ∈ O(n2).
1.10.2 Ω-notation
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.
The definition is illustrated in Fig. 1.9.

Fig. 1.9 Big-omega notation: t(n) ∈ Ω(g(n)).

Ω(g(n)), stands for the set of all functions with a higher or same order of growth as g(n) (to within a constant
multiple, as n goes to infinity). For example,

P4. Prove that n3 ∈ Ω(n2).

Let t(n) = n3 and g(n) = n2 .
n3 ≥ n2 for all n ≥ 0,
i.e., we can select c = 1 and n0 = 0.

P5. Show that:

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 25

P6. Show that: 5n2 + n ∈ Ω(n2).

1.10.3 Θ-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) for all n ≥ n0.
The definition is illustrated in Fig. 1.10.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 26

 Fig. 1.10 Big-theta notation: t(n) ∈ Θ(g(n)).
Θ(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).
P7. Prove that:

Let g(n) = n2, and

First, we prove the right inequality (the upper bound):

Second, we prove the left inequality (the lower bound):

Hence, we can select

P8. Prove that 100 n + 5 ∈ Θ(n).

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 27

1.10.4 Useful Property Involving the Asymptotic Notations
The following property is useful in analyzing 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
Since t1(n) ∈ O(g1(n)), there exist some positive constant c1 and some nonnegative integer n1 such that
t1(n) ≤ c1g1(n) for all n ≥ n1.
Similarly, since t2(n) ∈ O(g2(n)),
t2(n) ≤ c2g2(n) for all n ≥ n2.
Let 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)]
≤ c3 2 max{g1(n), g2(n)}.
Hence, t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}), with the constants required by the O definition being
c = 2c3 = 2 max{c1, c2}, and
n0 = max{n1, n2}, respectively.

For example, we can check whether an array has equal elements by the following two-part algorithm:
i) sort the array by applying some known sorting algorithm;
ii) scan the sorted array to check its consecutive elements for equality.

If a sorting algorithm used in the first part makes no more than comparisons (and hence is in
O(n2)) while the second part makes no more than n − 1 comparisons (and hence is in O(n)), the efficiency
of the entire algorithm will be in O(max{n2, n}) = O(n2).

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 28

1.10.5 Using Limits for Comparing Orders of Growth
A much more convenient method for comparing the orders of growth of two specific functions is based on
computing the limit of the ratio of two functions in question.
Three principal cases may arise:

The first two cases mean that t(n) ∈ O(g(n)),

the last two mean that t(n) ∈ Ω(g(n)), and
the second case means that t(n) ∈ Θ(g(n)).
The limit-based approach takes advantage of the powerful calculus techniques developed for computing
limits, such as
L'Hospital's rule:

Stirling’s formula:

P9. Compare the orders of growth of and n2.

Since the limit is equal to a positive constant, the functions have the same order of growth or, symbolically,

P10. Compare the orders of growth of log2n and √n.

Since the limit is equal to zero, log2n has a smaller order of growth than √n.

P11. Compare the orders of growth of n! and 2n.

Using Stirling’s formula,

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 29

 (

Thus, though 2n grows very fast, n! grows still faster. We can write symbolically that n! ∈ Ω(2n).

1.10.6 Basic Efficiency Classes

There are still infinitely many classes. For example, the exponential functions an have different orders of
growth for different values of base a. These classes are listed in Table 1.2 in increasing order of their orders
of growth, along with their names and a few comments.
TABLE 1.2 Basic asymptotic efficiency classes

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 30

1.11 Mathematical Analysis of Nonrecursive Algorithms
We systematically apply the general to analyze the time efficiency of nonrecursive algorithms.

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

Pseudocode
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

• The measure of an input’s size here is the number of elements in the array, i.e., n.
• The operations that are going to be executed most often are in the algorithm’s for loop.
• There are two operations in the loop’s body:
- the comparison A[i]> maxval and
- the assignment maxval←A[i].
Which of these two operations should we consider basic?
Since the comparison is executed on each repetition of the loop and the assignment is not, we should
consider the comparison to be the algorithm’s basic operation.
The number of comparisons will be the same for all arrays of size n; therefore, in terms of this metric, there
is no need to distinguish among the worst, average, and best cases here.
Let C(n) the number of times this comparison is executed.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 31

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,

1.11.2 General Plan for Analyzing the Time Efficiency of Nonrecursive 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 innermost 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.

1.11.3 Important formulae and rules

We use frequently two basic rules of sum manipulation:

And two summation formulae:

1.11.4 EXAMPLE 2
Consider the element uniqueness problem: check whether all the elements in a given array of n elements
are distinct.
Pseudocode:
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

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 32

 for i ←0 to n − 2 do
for j ←i + 1 to n − 1 do
if A[i]= A[j ] return false
return true

• The natural measure of the input’s size here is again n, the number of elements in the array.
• Since the innermost loop contains a single operation (the comparison of two elements), we should
consider it as the algorithm’s basic operation.
• 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.
• We will limit our investigation to the worst case only.
By definition, the worst-case input is an array for which the number of element comparisons Cworst(n) is the
largest among all arrays of size n.
An inspection of the innermost loop reveals that there are two kinds of worst-case inputs
- Inputs for which the algorithm does not exit the loop prematurely: arrays with no equal elements and
- arrays in which the last two elements are the only pair of equal elements.
For such inputs, 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.
Accordingly, we get

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

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,

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 33

j ≤ n − 1.
If A is an m × n matrix and B is an n × p matrix, the matrix product C = AB is defined to be
the m × p matrix such that

for i = 1, ..., m and j = 1, ..., p.

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
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
- The input’s size is measured by matrix order n.
- There are two arithmetical operations in the innermost loop here - multiplication and addition - that, in
principle, can compete for designation as the algorithm’s basic operation.
- Actually, we do not have to choose between them, because on each repetition of the innermost loop
each of the two is executed exactly once. So by counting one we automatically count the other.
- We consider multiplication as the basic operation.
- Let us set up a sum for the total number of multiplications M(n) executed by the algorithm.
- 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.
- 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. Therefore, the
number of multiplications made for every pair of specific values of variables i and j is

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

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 34

The running time of the algorithm on a particular machine,
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.
Note that the estimates differ only by their multiplicative constants and not by their order of growth.

1.11.6 EXAMPLE 4
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

- The most frequently executed operation here is not inside the while loop but rather the comparison n >
1 that determines whether the loop’s body will be executed.
- Since the number of times the comparison will be executed is larger than the number of repetitions of
the loop’s body by exactly 1, the choice is not that important.
- The loop variable takes on only a few values between its lower and upper limits; therefore, we have to
use an alternative way of computing the number of times the loop is executed.
- Since the value of n is about halved on each repetition of the loop, the answer should be about log2 n.
- The exact formula for the number of times the comparison n>1 will be executed is actually⌊log2 n⌋+1;
which is the number of bits in the binary representation of n.

1.12 Mathematical Analysis of Recursive Algorithms

1.12.1 EXAMPLE 1
Compute the factorial function F(n) = n! for an arbitrary nonnegative 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

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 35

 //Input: A nonnegative integer n
//Output: The value of n!
if n = 0 return 1
else return F(n − 1) ∗ n

- Indicator of this algorithm’s input size is n.

- The basic operation of the algorithm is multiplication,
- Let the number of executions of multiplication be denoted M(n).
- Since the function F(n) is computed according to the formula
F(n) = F(n − 1) . n for n > 0,
the number of multiplications M(n) needed to compute it must satisfy the equality

M(n − 1) multiplications are spent to compute F(n − 1), and one more multiplication is needed to multiply
the result by n.
The last equation defines the sequence M(n) that we need to find.
This equation defines M(n) not explicitly, i.e., as a function of n, but implicitly as a function of its value at
another point, namely n − 1. Such equations are called recurrence relations or, for brevity, recurrences.
Our goal now is to solve the recurrence relation M(n) = M(n − 1) + 1,
i.e., to find an explicit formula for M(n) in terms of n only.
To determine a solution uniquely, we need an initial condition that tells us the value with which the
sequence starts. We can obtain this value by inspecting the condition that makes the algorithm stop its
recursive calls:
if n = 0 return 1.
This tells us two things.
i) Since the calls stop when n = 0, the smallest value of n for which this algorithm is executed and hence
M(n) defined is 0.
ii) By inspecting the pseudocode’s exiting line, we can see that when n = 0, the algorithm performs no
multiplications. Therefore, the initial condition we are after is

Thus, we 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(0) = 0.
We are dealing here with two recursively defined functions.
The first is the factorial function F(n) itself; it is defined by the recurrence

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 36

 F(n) = F(n − 1) . n for every n > 0,
F(0) = 1.
The second is the number of multiplications M(n) needed to compute F(n) by the recursive algorithm.
M(n) is defined by recurrence that we need to solve now.
From the several techniques available for solving recurrence relations, we use what can be called the
method of backward substitutions.
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.
After inspecting the first three lines, we see an emerging pattern, which makes it possible to predict not only
the next line but also a general formula for the pattern:
M(n) = M(n − i) + i.
Since it is specified for n = 0, we have to substitute i = n in the pattern’s formula to get the ultimate result
of our backward substitutions:
M(n) = M(n − 1) + 1= . . . = M(n − i) + i = . . . = M(n − n) + n = n.
The simple iterative algorithm that accumulates the product of n consecutive integers requires the same
number of multiplications, and it does so without the overhead of time and space used for maintaining the
recursion’s stack.
Generalizing our experience with investigating the recursive algorithm for computing n!, we can now
outline a general plan for investigating recursive algorithms.

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

1.12.3 EXAMPLE 2
The Tower of Hanoi puzzle. In this puzzle, we (or mythical monks) 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.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 37

The problem has an elegant recursive solution, which is illustrated in Fig. 1.11.
To move n>1 disks from peg 1 to peg 3 (with peg 2 as auxiliary), we first move recursively n − 1 disks
from peg 1 to peg 2 (with peg 3 as auxiliary), then move the largest disk directly from peg 1 to peg 3, and,
finally, move recursively n − 1 disks from peg 2 to peg 3 (using peg 1 as auxiliary). Of course, if n = 1, we
simply move the single disk directly from the source peg to the destination peg.

Fig. 1.11Recursive solution to the Tower of Hanoi puzzle.

Let us apply the general plan outlined above to the Tower of Hanoi problem.
- The input’s size indicator is the number of disks n.
- The algorithm’s basic operation is moving one disk.
- The number of moves M(n) depends on n only, and we get the following recurrence equation for it:
M(n) = M(n − 1) + 1+ M(n − 1) for n > 1.
The initial condition M(1) = 1, the recurrence relation for the number of moves M(n):
M(n) = 2M(n − 1) + 1 for n > 1,
M(1) = 1.
We solve this recurrence by the method of backward substitutions:
M(n) = 2M(n − 1) + 1 substitute M(n − 1) = 2M(n − 2) + 1
= 2[2M(n − 2) + 1]+ 1 = 22M(n − 2) + 2 + 1 substitute M(n − 2) = 2M(n − 3) + 1
= 22[2M(n − 3) + 1]+ 2 + 1 = 23M(n − 3) + 22 + 2 + 1.
The pattern of the first three sums on the left suggests that the next one will be
24M(n − 4) + 23 + 22 + 2 + 1,
and generally, after i substitutions, we get
M(n) = 2iM(n − i) + 2i−1 + 2i−2 + . . . + 2 + 1= 2iM(n − i) + 2i − 1.
Since the initial condition is specified for n = 1, which is achieved for i = n − 1, we get the following formula
for the solution to recurrence:
M(n) = 2n−1M(n − (n − 1)) + 2n−1 − 1
= 2n−1M(1) + 2n−1 − 1= 2n−1 + 2n−1 − 1= 2.2n−1 − 1=2n − 1.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 38

Thus, we have an exponential algorithm, which will run for an unimaginably long time even for moderate
values of n.
When a recursive algorithm makes more than a single call to itself, it can be useful for analysis purposes to
construct a tree of its recursive calls. In this tree, nodes correspond to recursive calls, and we can label them
with the value of the parameter (or, more generally, parameters) of the calls.
For the Tower of Hanoi example, the recursive calls tree is given in Fig. 1.12. By counting the number of
nodes in the tree, we can get the total number of calls made by the Tower of Hanoi algorithm:

where l is the level in the tree in Fig. 1.12.

Fig. 1.12 Tree of recursive calls made by the recursive algorithm for the Tower of Hanoi puzzle.
The number agrees, as it should, with the move count obtained earlier.

1.12.4 EXAMPLE 3
Recursive version of the algorithm that finds the number of binary digits in the binary representation of a
positive decimal integer.
ALGORITHM BinRec(n)
//Input: A positive decimal integer n
//Output: The number of binary digits in n’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
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.
To solving such a recurrence, we assume n is a power of 2 i.e. n = 2k.
A(2k) = A(2k−1) + 1 for k > 0,

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 39

 A(20) = 0.
Now backward substitutions:
A(2k) = A(2k−1) + 1 substitute A(2k−1) = A(2k−2) + 1
= [A(2k−2) + 1] + 1= A(2k−2) + 2 substitute A(2k−2) = A(2k−3) + 1
k−3 k−3
= [A(2 ) + 1] + 2 = A(2 ) + 3 ...
...
= A(2k−i) + i
...
= A(2k−k) + k.
A(2k) = A(1) + k = k,
Since n = 2k , k = log2 n,
A(n) = log2 n ∈ Θ(log n).

1.13 Brute Force and Exhaustive Search

Brute force is a straightforward approach to solving a problem, usually directly based on the problem
statement and definitions of the concepts involved.
Examples of brute-force algorithms:
- the consecutive integer checking algorithm for computing gcd(m, n),
- and the definition-based algorithm for matrix multiplication
Though rarely a source of clever or efficient algorithms, the brute-force approach should not be overlooked
as an important algorithm design strategy.
1. Brute force is applicable to a very wide variety of problems.
2. For some important problems - e.g., sorting, searching, matrix multiplication, string matching - the
brute-force approach yields reasonable algorithms of at least some practical value with no limitation
on instance size.
3. The expense of designing a more efficient algorithm may be unjustifiable if only a few instances of
a problem need to be solved and a brute-force algorithm can solve those instances with acceptable
speed.
4. Even if too inefficient in general, a brute-force algorithm can still be useful for solving small-size
instances of a problem.
5. A brute-force algorithm can serve an important theoretical or educational purpose as a yardstick
with which to judge more efficient alternatives for solving a problem.
The brute-force approach can be applied to the problem of sorting: given a list of n orderable items (e.g.,
numbers, characters from some alphabet, character strings), rearrange them in nondecreasing order.
The two algorithms - selection sort and bubble sort - seem to be the two prime candidates.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 40

1.14 Selection Sort
1.14.1 Working
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.

1.14.2 Pseudocode
In this pseudocode of the algorithm, for simplicity, we assume 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
if A[j ]<A[min] min←j
swap A[i] and A[min]

1.14.3 Example
Sort the list 89, 45, 68, 90, 29, 34, 17 using selection sort algorithm.

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 41

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

1.14.4 Analysis
The analysis of selection sort is straightforward.
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 sum:

- Selection sort is a Θ(n2) algorithm on all inputs.

- However, 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.

1.15 Bubble Sort

Bubble sort is another brute-force application to the sorting problem.
1.15.1 Working
It compares adjacent elements of the list and exchanges 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 as:

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

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 42

//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]

1.15.3 Example
Sort the list 89, 45, 68, 90, 29, 34, 17 using bubble sort algorithm.

First two passes of bubble sort on the list 89, 45, 68, 90, 29, 34, 17.
- A new line is shown after a swap of two elements is done.
- The elements to the right of the vertical bar are in their final positions and are not considered in
subsequent iterations of the algorithm.

1.15.4 Analysis
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. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 43

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:

The first version of the algorithm obtained can often be improved by exploiting the following observation:
if a pass through the list makes no exchanges, the list has been sorted and we can stop the algorithm.
- The new version runs faster on some inputs.
- It is still in Θ(n2) in the worst and average cases.

1.16 Sequential Search

Applications of the brute-force strategy to the problem of searching:
i) The canonical problem of searching for an item of a given value in a given list.
ii) String-matching problem.

1.16.1 Working
Sequential search is a brute-force algorithm for the general searching problem.
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.

1.16.2 Pseudocode
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

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 44

while A[i] ≠ K do
i ←i + 1
if i < n return i
else return −1

1.16.3 Improvement
An improvement 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.

1.16.4 Analysis
Sequential search provides an excellent illustration of the brute-force approach, with its characteristic
strength (simplicity) and weakness (inferior efficiency).

The efficiency results obtained for the standard version of sequential search change for the enhanced version
varies only very slightly, so that the algorithm remains linear in both the worst and average cases.

1.17 Brute-Force String Matching

A brute-force algorithm for the string-matching problem:
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 (then the algorithm can stop)
or a mismatching pair is encountered.
In the case of a mismatch, 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.
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.

1.17.2 Pseudocode
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

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 45

 j ←j + 1
if j = m return i
return −1

1.17.3 Example

Example of brute-force string matching: The pattern’s characters that are compared with their text
counterparts are in bold type.
For this example, the algorithm shifts the pattern almost always after a single character comparison.
- The worst case is much worse: the algorithm may have to make all m comparisons before shifting the
pattern, and this can happen for each of the n − m + 1 tries.
- Thus, in the algorithm makes m(n − m + 1) character comparisons, which puts it in the O(nm) class.
For a typical word search in a natural language text, however, we should expect that most shifts would
happen after very few comparisons. Therefore, the average-case efficiency should be considerably better
than the worst-case efficiency.

Module 1 – Introduction and Review

Introduction and Examples: What is an Algorithm? Algorithm Specification, Examples from real life: Air
Travel, Xerox Shop, Document Similarity and types of algorithms.
Motivation for Performance Analysis using Examples: Bubble Sort, Selection Sort, Insertion Sort, String
Pattern Matching. Contrast performance analysis versus actual runs.
Performance Analysis Framework: Space complexity, Time complexity. Asymptotic Notations: Big-Oh
notation (O), Omega notation (Ω), Theta not - recursive and recursive Algorithms with Examples.

Text Book 1: Chapter 1.1,2.1-2.4,3.1,3.2 Digital Resource: D1

Dr. Josephine Prem Kumar, Dept. of CSE, CIT 2024-25 Page 46