ANALYSIS AND DESIGN OF ALGORITHMS

BCS401

Module 1 - Notes
Introduction: What is an Algorithm? It’s Properties. Algorithm Specification-using natural language,
using Pseudo code convention, Fundamentals of Algorithmic Problem solving, Analysis Framework-
Time efficiency and space efficiency, Worst-case, Best-case and Average case efficiency.

Performance Analysis: Estimating Space complexity and Time complexity of algorithms.

Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω), Theta notation ( ) with examples, Basic
efficiency classes, Mathematical analysis of Non-Recursive and Recursive Algorithms with Examples
problems.

Brute force design technique: Selection sort, sequential search, string matching algorithm with complexity
Analysis.

By,
Dr. Vinutha K
Assistant Professor
Dept. of Information Science & Engineering
BMS Institute of Technology, Bengaluru.
 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

Module Introduction
Module-1:
1.1Introduction
1.1.1 What is an Algorithm?
Algorithm
An algorithmis a finite sequence of unambiguous instructions to solve a particular
Algorithm:An
problem.

Input.. Zero or more quantities are externally supplied.

a. Output.. At least one quantity is produced.
b. Definiteness.. Each instruction
in is clear and unambiguous. It must be perfectly clear
what should be done.
c. Finiteness.. If we trace out the instruction of an algorithm, then for all cases, the
algorithm terminates after a finite number of steps.
d. Effectiveness.. Every instruction must be very basic so so that it can be carried out,
inprinciple,, by a person using only pencil and paper. It is not enough that each
operation be definite as in criterion c;
c it also must be feasible.
1.1.2. Algorithm Specification
An algorithm can be specified in
1) Simple English
2) Graphical representation like flow chart
3) Programming
rogramming language like c++/java
4) Combination of above methods.
Example: Combination
ombination of simple English and C++, the algorithm for selection sort is
specified as follows.

Example: In C++ the same algorithm can

ca be specified as follows. Here Type is a basic or user
defined data type.

Prepared by Harivinod N [Link] Page| 1.2

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

1.1.3. Analysis Framework

Measuring an Input’s Size
hat almost all algorithms run longeron larger inputs. For example, it takes
It is observed that
longer to sort larger arrays, multiply
multiply largermatrices, 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.
There are situations, where the choice of a parameter indicating an input size does matter.
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
spell
algorithm? If the algorithm examines individual characters of its input, then we should
s
measure the size by the number of characters; if it works by processing words, we should
count their number in the input.
We should make a special note about measuring the size of inputs for algorithms involving
properties of numbers (e.g., checking whether
wh a given integer n is prime). For such
algorithms, computer scientists prefer measuring size by the number b of bits in the n's binary
representation: log n 1. This metric usually gives a better idea about the efficiency
of algorithms in question.

Units for Measuring Running lime

To measure 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. This approach is both excessively difficult and, as we
shall see, usually unnecessary. The thing to do is to identify the most important operation of
the algorithm, called the basic operation,
operation the operation contributing the most to the total
running time, and compute the number of times the basic operation is executed.
For example, most sorting algorithms work by comparing elements (keys) of a list being
sortedd with each other; for such algorithms, the basic operation is a key comparison.
As another example, algorithms for matrix multiplication and polynomial evaluation
require two arithmetic operations: multiplication and addition.
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:

Unless n is extremely large or very small, the formula can give a reasonable estimate of the
algorithm's running time.
It is for these reasons that the efficiency analysis framework ignores multiplicative constants
and concentrates
ates on the count's order of growth to within a constant multiple for large-size
large
inputs.

Prepared by Harivinod N [Link] Page| 1.3

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

Orders of Growth
Why this emphasis on the count's order of growth for large input sizes? Because for f large
values of n, it is the function's order of growth that counts:
counts just look at table which contains
values of a few functions particularly important for analysis of algorithms.
Table: Values of several functions important for analysis of algorithms

Algorithms that require an exponential number of operations are practical

practical for solving only
problems of very small sizes.

1.2. Performance Analysis

There
here are two kinds of efficiency: time efficiency and space efficiency.
• Time efficiency indicates how fast an algorithm in question runs;
• Space
pace efficiency deals with the extra
extr space the algorithm requires.
In the early days of electronic computing, both resources time and space were at a premium.
The
he research experience has shown that for most problems, we can achieve much more
spectacular progress in speed than inspace. Therefore,
Therefore we primarily concentrate on time
efficiency.
1.2.1 Space complexity
Total amount of computer memory required by an algorithm to complete its execution is
called as space complexity of that algorithm.
algorithm The Space required by an algorithm is the sum
of following components
• A fixed part that is independent of the input and output. This includes memory space
for codes, variables, constants and so on.
on
• A variable part that depends on the input, output and recursion stack. ( We call these
parameters as instance characteristics)
ch
Space requirement S(P) of an algorithm P, S(P) = c + Sp where c is a constant depends on
the fixed part, Sp is the instance characteristics\
characteristics
Example-1: Consider following algorithm abc()

Here fixed component depends on the size of a, b and

and c. Also instance characteristics Sp=0

Prepared by Harivinod N [Link] Page| 1.4

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

Example-2: Let us consider the algorithm to find sum of array. For the algorithm given here
the problem instances are characterized by n,, the number of elements to be summed. The
space needed by a[ ]depends
depends on [Link] the space complexity can be written
ritten as;S
as; sum(n) ≥ (n+3);
n for a[ ], One each for n, i and s.

1.2.2 Time complexity

Usually, the execution time or run-time
run of the program is refereed as its time complexity
denoted by tp(instance characteristics).
characteristics) This is the sum of the time taken to execute all
instructions in the program. Exact estimation runtime iss a complex task, as the number of
instructions executed is dependent on the input data. Also different instructions will take
different time to execute. So for the estimation of the time complexity we count only the
number of program steps. We can determine the steps needed by a program to solve a
particular problem instance in two ways.
Method-1: Wee introduce a new variable count to the program which is initialized
ini to zero.
We also
lso introduce statements to increment count by an appropriate amount into the program.
So when each time original program executes, the count also incremented by the step count.
Example: Consider the algorithm sum(). After the introduction
duction of the count the program will
be as follows. We can estimate that invocation of sum() executes total number of 2n+3 steps.

Method-2: Determine
etermine the step count of an algorithm by building a table in which we list the
total number of steps contributed
tributed by each statement. An example is shown below.
below The code
will find the sum of n numbers

Prepared by Harivinod N [Link] Page| 1.5

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

Example:Matrix addition

The above method is both excessively difficult and, usually unnecessary.. The thing to do is to
identify the most important operation of the algorithm, called the basic operation,
operation the
operation contributing the most to the total running time, and compute the number of times
the basic operation is executed.
Trade-off
tradeoff involved in a problem, that is, it cannot
There is often a time-space-tradeoff cann be solved with
few computing time and low memory consumption. One has to make a compromise and to
exchange computing time for memory consumption or vice versa, depending on which
algorithm one chooses and how one parameterizes it.

1.3. Asymptotic Notations

ions
The
he efficiency analysis framework concentrates on the order of growth of an algorithm’s
algorithm’
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
notations: (big oh), Ω(big omega),
Θ (big theta) and o(little oh)
1.3.1. Big-Oh 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.

Informally, O(g(n)) is the set of all functions with a lower or same order of growth as g(n).
Note that the definition gives us a lot of freedom in choosing
choosing specific valuesfor constants c
and n0.

Examples: , 100 5 , 1
!
∉ , 0.00001 ∉ , 1 ∉

Prepared by Harivinod N [Link] Page| 1.6

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

Strategies to prove Big-O:

O: Sometimes the easiest way to prove
prove that f (n) = O(g(n)) is to take c
to be the sum of the positive coefficients off(n). We can usually ignore the negative
coefficients.

Example: To prove 100n + 5 ∈ O(n2)

100n + 5 ≤ 105n2. (c=105,
(c=10 n0=1)
Example: To prove n2 + n = O(n3)
Take c = 1+1=2, if n ≥n0=1, then n2 + n =
O(n3)

i) Prove 3n+2=O(n) ii) Prove 1000n2+100n-6 = O(n2)

1.3.2. Omega notation
Definition: A function t(n) is said to be in Ω(g(n)),
(g(n)),
denoted t(n)∈ Ω(g(n)), if t(n) is bounded below by
some positive constant multiple of g(n) for all al
large n,i.e., if there exist some positive constant c
and some nonnegative integer n0 suchthatt(n) ≥ c
g(n) for all n ≥ n0.

Here is an example of the formal proof that n3 ∈ Ω(n2):n3 ≥ n2 for all n ≥ 0, i.e., we can
select c = 1 and n0 = 0.

Example:

Example: To prove n3 + 4n2 = Ω(n2)

We see that, if n≥0, n3+4n2≥ n3≥ n2; Therefore n3+4n2 ≥ 1n2for alln≥0
Thus, we have shown that n3+4n2 =Ω(n2) where c = 1 & n0=0

1.3.3. Theta notation

A function t(n)
(n) is said to be in Θ(g(n)), denoted
t(n) ∈ Θ(g(n)),if
if t (n) is bounded both above and
below by some positive constant multiples ofg(n)
for all large n, i.e., if there exist some positive
constants c1 and c2 and somenonnegative integer
n0 such that
c2g(n) ≤ t(n) ≤c1g(n) for all n ≥ n0.

Prepared by Harivinod N [Link] Page| 1.7

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

Example: n2 + 5n + 7 = Θ(n2)

Strategies for Ω and Θ

• Proving that a f(n) = Ω(g(n))
(g(n)) often requires more thought.
– Quite often, we have to pick c < 1.
– A good strategy is to pick a value of c which you think will work, and determine
which value of n0 is needed.
– Being able to do a little algebra helps.
– We can sometimes simplify by ignoring terms of f(n) with the positive
coefficients.
• The following theorem shows us that proving f(n) = Θ(g(n))
(g(n)) is nothing new:
Theorem: f(n) = Θ(g(n))
Θ if and only iff(n) = O(g(n)) and f(n) = Ω(g(n)).
Thus, we just apply the previous two strategies.

Prepared by Harivinod N [Link] Page| 1.8

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

Theorem: If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)), then t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}).
(The analogous assertions are true for the Ω and Ө notations as well.)
Proof: The prooff extends to orders of growth the following simple fact aboutfour arbitrary
real numbers a1, b1, a2, b2: if a1 ≤ b1 and a2 ≤ b2, then a1 + a2 ≤ 2 max{b1, b2}.
Since t1(n) ∈ O(g1(n)), there exist some positive constant c1 and some 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 us denote c3 = max{c1, c2} and consider n ≥ max{n1, n2} so that we can use both
inequalities. Adding them yields the following:
t1(n) + t2(n) ≤ c1g1(n) + c2g2(n)
≤ c3 g1(n) + c3g2(n) = c3[g1(n) + g2(n)]
≤ c32 max{g1(n), g2(n)}.
Hence, t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}), with the constants c and n0 required by the O
definition being 2c3 = 2 max{c1, c2} and max{n1, n2}, respectively.

3.4. Little Oh The function f(n)=

f(n) o(g(n)) [ i.e f of n is a little oh of g of n ] if and only if
(
lim 0
%→' )
Example:

For comparing the order of growth limit is used

If the case-11 holds good in the above limit, we represent it by little-oh.

Prepared by Harivinod N [Link] Page| 1.9

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

1.3.5. Basic asymptotic efficiency

fficiency Classes
Class Name Comments

Prepared by Harivinod N [Link] Page| 1.10

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

1.3.6. Mathematical Analysis of Non-recursive

Non & Recursive Algorithms
Analysis of Non-recursive
recursive Algorithms
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
’s basic operation. (As a rule, it is located in 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,
worst
average-case,
case, and, if necessary, best-case
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 closedform
formula for the count or, at the very least, establish its order of growth.
Example-1:: To find maximum element in the given array

Here comparison is the basic operation. Note that number of comparisions will be same for
all arrays of size n. Therefore, no need to distinguish worst, best and average cases. Total
number of basic operations (comparison)
are,

Example-2:: To check whether all the elements in the given array are
are distinct

Here basic operation is comparison. The maximum no. of comparisons happen in the worst
case. (i.e. all the elements in the array are distinct and algorithms return true).
true
Total number of basic operations (comparison) in the worst case are,
Prepared by Harivinod N [Link] Page| 1.11
 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

* +
Other than the worst case, the total comparisons areless
are than . For example if the first
+
two elements of the array are equal, only one comparison is computed.
So in general C(n) =O(n2)
Example-3:: To perform matrix multiplication

Number of basic operations

(multiplications) is

Total running time:

Suppose if we take into account of addition; Algoritham also have same number of additions
A(n) = n3
Total running time:

Example-4:: To count the bits in the binary representation

Prepared by Harivinod N [Link] Page| 1.12

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

The basic
sic operation is count=count + 1 repeats no. of times
Analysis of Recursive Algorithms
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 varyon
different inputs of the same size; if it can, the worst-case,
worst case, average-case,
average andbest-case
efficiencies must be investigated [Link] up a recurrence relation, with wit an
appropriate initial condition, for thenumber of times the basic operation is executed.
4. Solve the recurrence or, at least, ascertain the order of growth of its solution.
Example-1

Since the function F(n) is computed according to the formula

The number of multiplications

ultiplicationsM(n) needed to compute it must satisfy the equality

Such equations are called recurrence relations

Condition that makes the algorithm stopif
stop n = 0 return 1. Thus recurrence relation and initial
conditionfor the algorithm’s number of multiplications
multipl M(n) can be stated as

We can use backward substitutions method to solve this

….

Prepared by Harivinod N [Link] Page| 1.13

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

Example-2: Tower of Hanoi [Link] In this puzzle, There are n disks of different sizes that
canslide onto any of three pegs. Initially, all the disks are on the
the first peg in order ofsize, the
largest on the bottom and the smallest on top. The goal is to move all thedisks to the third
peg, using the second one as an auxiliary, if necessary. We canmove only one disk at a time,
and it is forbidden to place a larger disk on top of asmaller [Link] problem has an elegant
recursive solution, which is illustrated in Figure.
1. Iff n = 1, we move the single disk directly from the source peg to the destination peg.
2. To move n>1 disks from peg 1 to peg 3 (with peg 2 as auxiliary),
auxilia
o we first move recursively n-1 disks from peg 1 to peg 2 (with peg 3 as auxiliary),
o then move the largest disk directly from peg 1 to peg 3, and,
o finally, move recursively n-1
n 1 disks from peg 2 to peg 3 (using peg 1 as auxiliary).

Figure: Recursive
Recursive solution to the Tower of Hanoi puzzle

Algorithm: TowerOfHanoi(n, source, dest, aux)

If n == 1, THEN
move disk from source to dest
else
TowerOfHanoi (n - 1, source, aux, dest)
move disk from source to dest
TowerOfHanoi (n - 1, aux, dest, source)
End if

Computation of Number of Moves

The number of moves M(n) depends only on n. The recurrence equation is

Wee have the following recurrence relation for the number of moves M(n):

We solve this recurrence by the same method of backward substitutions:

Prepared by Harivinod N [Link] Page| 1.14

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

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

Since the initial condition is specified for n = 1, which is

is achieved for i = n-1, weget the
following formula for the solution to recurrence,
recurrence

Example-3:: To count bits of a decimal number in its binary representation

The recurrence relation can be written as

.
Also note that A(1) = 0.

oach to solving such a recurrence is to solve it only for n = 2k and then

The standard approach
take advantage of the theorem called the smoothness rule which claims that under very
broad assumptions the order of growth observed for n = 2k gives a correct answer about the
order of growth for all values of n.

Prepared by Harivinod N [Link] Page| 1.15

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

1.4.. Important Problem Types

In this section, we are going to introduce the most important problem types: Sorting,
Searching, String processing,, Graph problems, Combinatorial problems.
1.4.1. Sorting
The sorting problem is to rearrange the items of a given list in non-decreasing
decreasing order. As a
practical matter, we usually need to sort lists of numbers, characters from an alphabet or
character strings. Although some algorithms are indeed better than others, there is
noalgorithm m that would be the best solution in all situations. Some of the algorithms are
simple but relatively slow, while others are faster but more complex; some work better on
randomly ordered inputs, while others do better on almost-sorted
almost lists; some are suitable only
for lists residing in the fast memory, while others can be adapted for sorting large files stored
on a disk; and so on.
Two properties of sorting algorithms deserve special mention. A sorting algorithm is called
stable if it preserves the relative order
orde of any two equal elements in its input. The second
notable feature of a sorting algorithm is the amount of extra memory the algorithm requires.
An algorithm is said to be in-place
place if it does not require extra memory, except, possibly, for a
few memory units.
1.4.2. Searching
The searching problem deals with finding a given value, called a search key, in a given set.
(or a multiset, which permits several elements to have the same value).There are plenty of
searching algorithms to choose from. They range from the t straight forward sequential search
to a spectacularly efficient but limited binary search and algorithms based on representing
the underlying set in a different form more conducive to searching. The latter algorithms are
of particular importance for real-world
real rld applications because they are indispensable for storing
and retrieving information from large databases.
1.4.3. String Processing
In recent decades, the rapid proliferation of applications dealing with non-
non-numerical data has
intensified the interest of researchers
researchers and computing practitioners in string-handling
algorithms. A string is a sequence of characters from an alphabet. String-processing
algorithms have been important for computer science in conjunction with computer
languages and compiling issues.
1.4.4. Graph Problems
One of the oldest and most interesting areas in algorithmics is graph algorithms. Informally, a
graph can be thought of as a collection of points called vertices, some of which are connected
by line segments called edges.
edges Graphs can be used for modeling a wide variety of
applications, including transportation, communication, social and economic networks, project
scheduling, and games. Studying different technical and social aspects of the Internet in
particular is one of the active areas of current
curr research involving computer scientists,
economists, and social scientists.
scientists

Prepared by Harivinod N [Link] Page| 1.16

 Lecture Notes | 18CS42
18CS4 – DAA | Module 1: Introduction

1.4.5. Combinatorial Problems

Generally speaking, combinatorial problems are the most difficult problems in computing,
from both a theoretical and practical standpoint. Their difficulty
difficulty stems from the following
facts. First, the number of combinatorial objects typically grows extremely fast with a
problem’s size, reaching unimaginable magnitudes even for moderate-sized
moderate instances.
Second, there are no known algorithms for solving most most such problems exactly in an
acceptable amount of time.

1.5.. Fundamental Data Structures

Since the vast majority of algorithms of interest operate on data, particular ways of
organizing data play a critical role in the design and analysis of algorithms.
algorithms A data structure
can be defined as a particular scheme of organizing related data items.
1.5.1. Linear Data Structures
The two most important elementary data structures are the array and the linked list.
A(one-dimensional) array is a sequence of n items of the same data type that are stored
contiguously in computer memory and made accessible by specifying a value of the array’s
index.

A linked list is a sequence of zero or more elements called nodes, each containing two kinds
of information: some data and one or more links called pointers to other nodes of the linked
list. In a singly linked list,, each node except the last one contains a single pointer to the next
element. Another extension is the structure called the doubly linked list, list in which every
node, except
xcept the first and the last, contains pointers to both its successor and its predecessor.

A list is a finite sequence of data items, i.e., a collection of data items arranged in a certain
linear order. The basic operations performed on this data structure structure are searching for,
inserting, and deleting an element. Two special types of lists, stacks and queues, are
particularly important.
A stack is a list in which insertions and deletions can be done only at the end. This end is
called the top because a stack
ck is usually visualized not horizontally but vertically—akin
vertically to a
stack of plates whose “operations” it mimics very closely.

Prepared by Harivinod N [Link] Page| 1.17

 BRUTE FORCE
Brute Force

“Brute force is a straightforward approach to solving a problem, usually directly

based the problem statement and definitions of the concepts involved.”
The “force” implied by the strategy’s definition is that of a computer and not that of one’s intellect.
And often, the brute-force strategy is indeed the one that is easiest to apply. As an example, consider
the exponentiation problem: compute an for a nonzero number a and a nonnegative integer n.
Although this problem might seem trivial, it provides a useful vehicle for illustrating several
algorithm design strategies, including the brute force .

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 elements and exchange it with the second element, putting the second smallest element in its final
position.
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]

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 following sum:
 Sequential Search
We have already encountered a brute-force algorithm for the general searching problem: it
is called sequential search. To repeat, the algorithm simply compares successive elements of a given
list with a given search key until either a match is encountered (successful search) or the list is
exhausted without finding a match (unsuccessful search). A simple extra trick is often employed in
implementing sequential search: if we append the search key to the end of the list, the search for the
key will have to be successful, and therefore we can eliminate the end of list check altogether. Here
is pseudo code of this enhanced version.
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

Input size: n
Basic op: <, ≠

Cworst(n) = n

Another straightforward improvement can be incorporated in sequential search if a given list

is known to be sorted: searching in such a list can be stopped as soon as an element greater than or
equal to the search key is encountered. 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 only very slightly, so that the algorithm remains linear in both the worst and average cases.

Brute-Force String Matching

Recall the string-matching problem introduced in earlier section: given a string of n
characters called the text and a string of m characters (m ≤ n) called the pattern, find a substring of
the text that matches the pattern. To put it more precisely, we want to find i—the index of the
leftmost character of the first matching substring in the text—such that
ti= p0, . . . , ti+j = pj, . . . , ti+m−1 = pm−1:
 If matches other than the first one need to be found, a string-matching algorithm
can simply continue working until the entire text is exhausted.

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

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

Note that 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.
ALGORITHM BruteForceStringMatch(T [0..n − 1], P[0..m − 1])
//Implements brute-force string matching
//Input: An array T [0..n − 1] of n characters representing a text and
// an array P[0..m − 1] of m characters representing a pattern
//Output: The index of the first character in the text that starts a
// matching substring or −1 if the search is unsuccessful
for i ←0 to n − m do

j ←0

while j <m and P[j ]= T [i + j ] do

←j + 1

if j = m return i

return −1

Note that for the 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

Time efficiency: Θ(mn) comparisons (in the worst case)