INTRODUCTION

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

Problem to be solved

Algorithm

Input Computer Program Output

It is a step by step procedure with the input to solve the problem in a finite amount of time
to obtain the required output.

The notion of the algorithm illustrates some important points:

 The non-ambiguity requirement for each step of an algorithm cannot be compromised.
 The range of inputs for which an algorithm works has to be specified carefully.
 The same algorithm can be represented in several different ways.
 There may exist several algorithms for solving the same problem.
 Algorithms for the same problem can be based on very different ideas and can solve the
problem with dramatically different speeds.

Characteristics of an algorithm:
Input: Zero / more quantities are externally supplied.
Output: At least one quantity is produced.
Definiteness: Each instruction is clear and unambiguous.
Finiteness: If the instructions of an algorithm is traced then for all cases the algorithm must
terminates after a finite number of steps.
Efficiency: Every instruction must be very basic and runs in short time.

Example:
The greatest common divisor(GCD) of two nonnegative integers m and n (not-both-zero),
denoted gcd(m, n), is defined as the largest integer that divides both m and n evenly, i.e., with a
remainder of zero.

Euclid’s algorithm is based on applying repeatedly the equality gcd(m, n) = gcd(n, m mod n),
where m mod n is the remainder of the division of m by n, until m mod n is equal to 0. Since gcd(m,
0) = m, the last value of m is also the greatest common divisor of the initial m and n.
gcd(60, 24) can be computed as follows:gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.

Euclid’s algorithm for computing gcd(m, n) in simple steps

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.

Euclid’s algorithm for computing gcd(m, n) expressed in pseudocode

ALGORITHM Euclid_gcd(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

FUNDAMENTALS OF ALGORITHMIC PROBLEM SOLVING

A sequence of steps involved in designing and analyzing an algorithm is shown in the figure
below.

(i) Understanding the Problem

 This is the first step in designing of algorithm.
 Read the problem’s description carefully to understand the problem statement completely.
 Ask questions for clarifying the doubts about the problem.
 Identify the problem types and use existing algorithm to find solution.
 Input (instance) to the problem and range of the input get fixed.

(ii) Decision making

The Decision making is done on the following:
(a) Ascertaining the Capabilities of the Computational Device
 In random-access machine (RAM), instructions are executed one after another (The
central assumption is that one operation at a time). Accordingly, algorithms
designed to be executed on such machines are called sequential algorithms.
  In some newer computers, operations are executed concurrently, i.e., in parallel.
Algorithms that take advantage of this capability are called parallel algorithms.
 Choice of computational devices like Processor and memory is mainly based on
space and time efficiency
(b) Choosing between Exact and Approximate Problem Solving
 The next principal decision is to choose between solving the problem exactly or
solving it approximately.
 An algorithm used to solve the problem exactly and produce correct result is called
an exact algorithm.
If the problem is so complex and not able to get exact solution, then we have to
choose an algorithm called an approximation algorithm. i.e., produces an
approximate answer. Eg: extracting square roots, solving nonlinear equations, and
evaluating definite integrals.
(c) Algorithm Design Techniques
 An algorithm design technique (or “strategy” or “paradigm”) is a general approach
to solving problems algorithmically that is applicable to a variety of problems from
different areas of computing.
 Algorithms+ Data Structures =
 Though Algorithms and Data Structures are independent, but they are combined
together to develop program. Hence the choice of proper data structure is required
before designing the algorithm.
 Implementation of algorithm is possible only with the help of Algorithms and Data
Structures
 Algorithmic strategy / technique / paradigm are a general approach by which
many problems can be solved algorithmically. E.g., Brute Force, Divide and
Conquer, Dynamic Programming, Greedy Technique and so on.

(iii) Methods of Specifying an Algorithm

There are three ways to specify an algorithm. They are:

a. Natural language
b. Pseudocode
c. Flowchart
Algorithm Specification

Natural Language Pseudocode Flowchart

Pseudocode and flowchart are the two options that are most widely used nowadays for specifying
algorithms.

a. Natural Language
It is very simple and easy to specify an algorithm using natural language. But many times
specification of algorithm by using natural language is not clear and thereby we get brief
specification.
Example: An algorithm to perform addition of two numbers.
Such a specification creates difficulty while actually implementing it. Hence many programmers
Step 1: Readofthe
prefer to have specification first number,
algorithm say of Pseudocode.
by means
a. Step 2: Read the first number,
b. Pseudocodesay b.
 PseudocodeStepis3:aAdd
mixture of a natural
the above language
two numbers and
and programming
store the result inlanguage constructs.
Pseudocode is usually more precise than natural language.
 For Assignment operation left arrow “←”, for comments two slashes “//”,if condition, for,
 while loops are used.

This specification is more useful for implementation of any language.

ALGORITHM Sum(a,b)
//Problem Description: This algorithm performs addition of two numbers
c. Flowchart
//Input: Two integers a and b
In the earlier days of computing, the dominant method for specifying algorithms was a flowchart,
//Output: Addition of two integers
this representation technique has proved to be inconvenient.
c←a+b
Flowchart is a graphical representation of an algorithm. It is a a method of expressing an algorithm
return
by a collection of c
connected geometric shapes containing descriptions of the algorithm’s steps.
Symbols Example: Addition of a and b

Start Start state

Start
Transition / Assignment
Input the value of a

Processing / Input read

Input the value of b
Input and Output
c=a+b

Condition / Decision
Display the value of c

Flow connectivity
Stop
Stop Stop state

FIGURE 1.4 Flowchart symbols and Example for two integer addition.

(iv) Proving an Algorithm’s Correctness

 Once an algorithm has been specified then its correctness must be proved.
 An algorithm must yields a required result for every legitimate input in a finite amount of
time.
  For example, the correctness of Euclid’s algorithm for computing the greatest common
divisor stems from the correctness of the equality gcd(m, n) = gcd(n, m mod n).
 A common technique for proving correctness is to use mathematical induction because an
algorithm’s iterations provide a natural sequence of steps needed for such proofs.
 The notion of correctness for approximation algorithms is less straightforward than it is for
exact algorithms. The error produced by the algorithm should not exceed a predefined
limit.

(v) Analyzing an Algorithm

 For an algorithm the most important is efficiency. In fact, there are two kinds of algorithm
efficiency. They are:
 Time efficiency, indicating how fast the algorithm runs, and
 Space efficiency, indicating how much extra memory it uses.
 The efficiency of an algorithm is determined by measuring both time efficiency and space
efficiency.
 So factors to analyze an algorithm are:
 Time efficiency of an algorithm
 Space efficiency of an algorithm
 Simplicity of an algorithm
 Generality of an algorithm

(vi) Coding an Algorithm

 The coding / implementation of an algorithm is done by a suitable programming language
like C, C++, JAVA.
 The transition from an algorithm to a program can be done either incorrectly or very
inefficiently. Implementing an algorithm correctly is necessary. The Algorithm power
should not reduced by inefficient implementation.
 Standard tricks like computing a loop’s invariant (an expression that does not change its
value) outside the loop, collecting common subexpressions, replacing expensive
operations by cheap ones, selection of programming language and so on should be known to
the programmer.
 Typically, such improvements can speed up a program only by a constant factor, whereas a
better algorithm can make a difference in running time by orders of magnitude. But once
an algorithm is selected, a 10–50% speedup may be worth an effort.
 It is very essential to write an optimized code (efficient code) to reduce the burden of
compiler.

IMPORTANT PROBLEM TYPES

The most important problem types are:
(i). Sorting
(ii). Searching
(iii). String processing
(iv). Graph problems
(v). Combinatorial problems
(vi). Geometric problems
(vii). Numerical problems
(i) Sorting
 The sorting problem is to rearrange the items of a given list in nondecreasing (ascending)
order.
 Sorting can be done on numbers, characters, strings or records.
 To sort student records in alphabetical order of names or by student number or by student
grade-point average. Such a specially chosen piece of information is called a key.
 An algorithm is said to be in-place if it does not require extra memory, E.g., Quick sort.
 A sorting algorithm is called stable if it preserves the relative order of any two equal
elements in its input.

(ii) Searching
 The searching problem deals with finding a given value, called a search key, in a given set.
 E.g., Ordinary Linear search and fast binary search.

(iii) String processing

 A string is a sequence of characters from an alphabet.
 Strings comprise letters, numbers, and special characters; bit strings, which comprise zeros
and ones; and gene sequences, which can be modeled by strings of characters from the four-
character alphabet {A, C, G, T}. It is very useful in bioinformatics.
 Searching for a given word in a text is called string matching

(iv) Graph problems

 A graph is a collection of points called vertices, some of which are connected by line
segments called edges.
 Some of the graph problems are graph traversal, shortest path algorithm, topological sort,
traveling salesman problem and the graph-coloring problem and so on.

(v) Combinatorial problems

 These are problems that ask, explicitly or implicitly, to find a combinatorial object such as a
permutation, a combination, or a subset that satisfies certain constraints.
 A desired combinatorial object may also be required to have some additional property such
s a maximum value or a minimum cost.
 In practical, the combinatorial problems are the most difficult problems in computing.
 The traveling salesman problem and the graph coloring problem are examples of
combinatorial problems.

(vi) Geometric problems

 Geometric algorithms deal with geometric objects such as points, lines, and polygons.
 Geometric algorithms are used in computer graphics, robotics, and tomography.
 The closest-pair problem and the convex-hull problem are comes under
this category.

(vii) Numerical problems

 Numerical problems are problems that involve mathematical equations, systems of
equations, computing definite integrals, evaluating functions, and so on.
 The majority of such mathematical problems can be solved only approximately.
 Fundamental Data Structures

A data structure can be defined as a particular scheme of organizing related data items. The nature of
the data items is dictated by a problem at hand; they can range from elementary data types (e.g.,
integers or characters) to data structures (e.g., a one-dimensional array of one-dimensional arrays is
often used for implementing matrices).

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 .
In the majority of cases, the index is an integer either between 0 and n - 1 or between 1 and n.
Some computer languages allow an array index to range between any two integer bounds low and
high, and some even permit non-numerical indices to specify, for example, data items corresponding
to the 12 months of the year by the month names.

Each and every element of an array can be accessed in the same constant amount of time regardless of
where in the array the element in question is located. This feature positively distinguishes arrays from
linked lists . It is also assumed that every element of an array occupies the same amount of computer
storage.
Arrays are used for implementing a variety of other data structures. Prominent among them is the
string, a sequence of characters from an alphabet terminated by a special character indicating the
string's end. Strings composed of zeros and ones are called binary strings or bit strings. Operations
we usually perform on strings differ from those we typically perform on other. They include
computing the string length, comparing two strings to determine which one precedes the other
according to the so-called lexicographic order, i.e., in a dictionary, and concatenating two strings .
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. (A
special pointer called "null" is used to indicate the absence of a node's successor.) In a singly linked
list, each node except the last one contains a single pointer to the next element.

To access a particular node of a linked list, we start with the list's first node and traverse the pointer
chain until the particular node is reached. Thus, the time needed to access an element of a singly
linked list, unlike that of an array, depends on where in the list the element is located. On the positive
side, linked lists do not require any preliminary reservation of the computer memory, and insertions
and deletions can be made quite efficiently in a linked list by reconnecting a few appropriate pointers.
Another extension is the structure called the doubly linked list, in which every node, except the
first and the last, contains pointers to both its successor and its predecessor.

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 is
usually visualized not horizontally but vertically. As a result, when elements are added to (pushed
onto) a stack and deleted from (popped off) it, the structure operates in the "last-in-first-out" (LIFO)
fashion, exactly as the stack of plates does if we can remove only the top plate or add another plate to
top of the stack. Stacks have a multitude of applications; in particular, they are indispensable for
implementing recursive algorithms.

A queue, on the other hand, is a list from which elements are deleted from one end of the structure,
called the front (this operation is called dequeue), and new elements are added to the other end,
called the rear (this operation is called enqueue). Consequently, a queue operates in the "first -in-
first-out" (FIFO) fashion. Queues also have many important applications, including several
algorithms for graph problems.

The principal operations on a priority queue are finding its largest element, deleting its largest
element, and adding a new element. Of course, a priority queue must be implemented so that the last
two operations yield another priority queue. Straightforward implementations of this data structure
can be based on either an array or a sorted array, but neither of these options yields the most efficient
solution possible. A better implementation of a priority queue is based on an ingenious data structure
called the heap.

Graphs
A graph is a collection of points in the plane called "vertices" or "nodes," some of them connected
by line segments called "edges" or "arcs." Formally, a graph G = {V, E) is defined by a pair of two
sets: a finite set V of items called vertices and a set E of pairs of these items called edges. lf these
pairs of vertices are unordered, i.e., a pair of vertices (u, v) is the same as the pair (v, u), we say that
the vertices u and v are adjacent to each other and that they are connected by the undirected edge (u,
v). We call the vertices u and v endpoints of the edge (u, v) and say that u and v are incident to this
edge; we also say that the edge (u, v) is incedent to its endpoints u and v. A graph G is called
undirected if every edge in it is undirected.

If a pair of vertices (u, v) is not the same as the pair (v, u), we say that the edge (u, v) is directed from
the vertex u, called the edge's tail, to the vertex v, called the edge's head. We also say that the edge (u,
v) leaves u and enters v. A graph whose every edge is directed is called directed. Directed graphs are
also called digraphs.
It is normally convenient to label vertices of a graph or a digraph with letters, integer numbers, or, if
an application calls for it, character strings.

The graph in figure(a) has six vertices and seven edges:

V ={a, b, c, d, e, f), E ={(a, c), (a, d), (b, c), (b, f), (c, e), (d, e), (e, f)).
The digraph in Figure (b) has six vertices and eight directed edges:
V ={a, b, c, d, e, f),
E ={(a, c), (b, c), (b, f), (c, e), (d, a), (d, e), (e, c), (e, f)).
Edges connecting vertices to themselves are called loops.
A graph with every pair of its vertices connected by an edge is called complete. A standard
notation for the complete graph with |V| vertices is K|V|· A graph with relatively few possible edges
missing is called dense; a graph with few edges relative to the number of its vertices is called sparse.

Graph representations
Graphs for computer algorithms can be represented in two principal ways: the adjacency matrix and
adjacency lists. The adjacency matrix of a graph with n vertices is an n-by-n boolean matrix with one
row and one column for each of the graph's vertices, in which the element in the ith row and the jth
column is equal to 1 if there is an edge from the ith vertex to the jth vertex, and equal to 0 if there is no
such edge.

The adjacency lists of a graph or a digraph is a collection of linked lists, one for each vertex, that
contain all the vertices adjacent to the list's vertex (i.e., all the vertices connected to it by an edge).
Usually, such lists start with a header identifying a vertex for which the list is compiled.

Weighted graphs
A weighted graph (or weighted digraph) is a graph (or digraph) with numbers assigned to its edges.
These numbers are called weights or costs. An interest in such graphs is motivated by numerous real-
life applications, such as finding the shortest path between two points in a transportation or
communication network or the traveling salesman problem mentioned earlier.
If a weighted graph is represented by its adjacency matrix, then its element A[i, j] will simply
contain the weight of the edge from the ith to the jth vertex if there is such an edge and a special
symbol, e.g., ∞, if there is no such edge. Such a matrix is called the weight matrix or cost matrix.

Adjacency lists for a weighted graph have to include in their nodes not only the name of an adjacent
vertex but also the weight of the corresponding edge.

Paths and cycles

Two important applications of graph are: connectivity and acyclicity. Both are based on the notion of
a path. A path from vertex u to vertex v of a graph G can be defined as a sequence of adjacent
(connected by an edge) vertices that starts with u and ends with v. If all vertices of a path are distinct,
the path is said to be simple. The length of a path is the total number of vertices in a vertex sequence
defining the path minus one, which is the same as the number of edges in the path. For example, a, c,
b, f is a simple path of length 3 from a to fin the graph of Figure 1.6a, whereas a, c, e, c, b, f is a path
(not simple) of length 5 from a to f.
In the case of a directed graph, we are usually interested in directed paths. A directed path is a
sequence of vertices in which every consecutive pair of the vertices is connected by an edge directed
from the vertex listed first to the vertex listed next.

For example, a, c, e, f is a directed path from a to f in the graph.

A graph is said to be connected if for every pair of its vertices u and v there is a path from u to v.

A cycle is a path of a positive length that starts and ends at the same vertex and does not traverse the
same edge more than once.

FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM EFFICIENCY

The efficiency of an algorithm can be in terms of time and space. The algorithm efficiency
can be analyzed by the following ways.
a. Analysis Framework.
b. Asymptotic Notations and its properties.
c. Mathematical analysis for Recursive algorithms.
d. Mathematical analysis for Non-recursive algorithms.

Analysis Framework
There are two kinds of efficiencies to analyze the efficiency of any algorithm. They are:
 Time efficiency, indicating how fast the algorithm runs, and
 Space efficiency, indicating how much extra memory it uses.
The algorithm analysis framework consists of the following:
 Measuring an Input’s Size
 Units for Measuring Running Time
 Orders of Growth
 Worst-Case, Best-Case, and Average-Case Efficiencies

(i) Measuring an Input’s Size

 An algorithm’s efficiency is defined as a function of some parameter n indicating the
algorithm’s input size. In most cases, selecting such a parameter is quite straightforward.
For example, it will be the size of the list for problems of sorting, searching.
 For the problem of evaluating a polynomial p(x) = anxn + . . . + a0 of degree n, the size of
the parameter will be the polynomial’s degree or the number of its coefficients, which is
larger by 1 than its degree.
 In computing the product of two n × n matrices, the choice of a parameter indicating an
input size does matter.
 Consider a spell-checking algorithm. If the algorithm examines individual characters of its
input, then the size is measured by the number of characters.
 In measuring input size for algorithms solving problems such as checking primality of a
positive integer n. the input is just one number.
 The input size by the number b of bits in the n’s binary representation is b=(log2 n)+1.

(ii) Units for Measuring Running Time

Some standard unit of time measurement such as a second, or millisecond, and so on can be
used to measure the running time of a program after implementing the algorithm.
Drawbacks
 Dependence on the speed of a particular computer.
 Dependence on the quality of a program implementing the algorithm.
 The compiler used in generating the machine code.
 The difficulty of clocking the actual running time of the program.
So, we need metric to measure an algorithm’s efficiency that does not depend on these
extraneous factors.
One possible approach is to count the number of times each of the algorithm’s operations
is executed. This approach is excessively difficult.
The most important operation (+, -, *, /) of the algorithm, called the basic operation.
Computing the number of times the basic operation is executed is easy. The total running time is
determined by basic operations count.

(iii) Orders of Growth

 A difference in running times on small inputs is not what really distinguishes efficient
algorithms from inefficient ones.
 For example, the greatest common divisor of two small numbers, it is not immediately clear
how much more efficient Euclid’s algorithm is compared to the other algorithms, the
difference in algorithm efficiencies becomes clear for larger numbers only.
 For large values of n, it is the function’s order of growth that counts just like the Table 1.1,
which contains values of a few functions particularly important for analysis of algorithms.

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

n √𝑛 log2n n n log2n n2 n3 2n n!
1 1 0 1 0 1 1 2 1
 2 1.4 1 2 2 4 4 4 2
4 2 2 4 8 16 64 16 24
8 2.8 3 8 2.4•101 64 5.1•102 2.6•102 4.0•104
10 3.2 3.3 10 3.3•101 102 103 103 3.6•106
16 4 4 16 6.4•101 2.6•102 4.1•103 6.5•104 2.1•1013
102 10 6.6 102 6.6•102 104 106 1.3•1030 9.3•10157
103 31 10 103 1.0•104 106 109
104 102 13 104 1.3•105 108 Very big
1012
105 3.2•102 17 105 1.7•106 10 computation
10 1015
106 103 20 106 2.0•107 1012 1018

(iv) Worst-Case, Best-Case, and Average-Case Efficiencies

Consider Sequential Search algorithm some search key K
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
Clearly, the running time of this algorithm can be quite different for the same list size n.

In the worst case, there is no matching of elements or the first matching element can found
at last on the list. In the best case, there is matching of elements at first on the list.

Worst-case efficiency
 The worst-case efficiency of an algorithm is its efficiency for the worst case input of size n.
 The algorithm runs the longest among all possible inputs of that size.
 For the input of size n, the running time is Cworst(n) = n.

Best case efficiency

 The best-case efficiency of an algorithm is its efficiency for the best case input of size n.
 The algorithm runs the fastest among all possible inputs of that size n.
 In sequential search, If we search a first element in list of size n. (i.e. first element equal to
a search key), then the running time is Cbest(n) = 1

Average case efficiency

 The Average case efficiency lies between best case and worst case.
 To analyze the algorithm’s average case efficiency, we must make some assumptions about
possible inputs of size n.
 The standard assumptions are that
o The probability of a successful search is equal to p (0 ≤ p ≤ 1) and
 o The probability of the first match occurring in the ith position of the list is the same
for every i.

Yet another type of efficiency is called amortized efficiency. It applies not to a single run of
an algorithm but rather to a sequence of operations performed on the same data structure.

ASYMPTOTIC NOTATIONS AND ITS PROPERTIES

Asymptotic notation is a notation, which is used to take meaningful statement about the
efficiency of a program.
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, they
are:
 O - Big oh notation
 Ω - Big omega notation
 Θ - Big theta notation
Let t(n) and g(n) can be any nonnegative functions defined on the set of natural numbers.
The algorithm’s running time t(n) usually indicated by its basic operation count C(n), and g(n),
some simple function to compare with the count.

Example 1:

where g(n) = n2.

A function t(n) is said to be in O(g(n)), denoted 𝑡 (𝑛) ∈ 𝑂(𝑔(𝑛)), if t (n) is bounded

(i) O - Big oh notation

above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c

𝑡 (𝑛) ≤ (𝑛) fo𝑟 𝑎𝑙𝑙 𝑛 ≥ 𝑛0.

and some nonnegative integer n0 such that

Where t(n) and g(n) are nonnegative functions defined on the set of natural numbers.
O = Asymptotic upper bound = Useful for worst case analysis = Loose bound
FIGURE 1.5 Big-oh notation: 𝑡 (𝑛) ∈ ((𝑛)).

Example 2: Prove the assertions 100𝑛 + 5 ∈ (𝑛2).

Proof: 100n + 5 ≤ 100n + n (for all n ≥ 5)
= 101n
≤ 101n2 (Ӭ 𝑛 ≤ 𝑛2)
Since, the definition gives us a lot of freedom in choosing specific values for constants c

Example 3: Prove the assertions 100𝑛 + 5 ∈ (𝑛).

and n0. We have c=101 and n0=5

Proof: 100n + 5 ≤ 100n + 5n (for all n ≥ 1)

= 105n
i.e., 100n + 5 ≤ 105n
i.e., t(n) ≤
cg(n)
±100𝑛 + 5 ∈ (𝑛) with c=105 and n0=1

A function t(n) is said to be in Ω(g(n)), denoted t(n) ∈ Ω(g(n)), if t(n) is bounded below by
(ii) Ω - Big omega notation

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.
Where t(n) and g(n) are nonnegative functions defined on the set of natural numbers.
Ω = Asymptotic lower bound = Useful for best case analysis = Loose bound
FIGURE 1.6 Big-omega notation: t (n) ∈ Ω (g(n)).

Example 4: Prove the assertions n3+10n2+4n+2 ∈ Ω (n2).

Proof: n3+10n2+4n+2 ≥ n2 (for all n ≥ 0)
i.e., by definition t(n) ≥ cg(n), where c=1 and n0=0

A function t(n) is said to be in Θ(g(n)), denoted t(n) ∈ Θ(g(n)), if t(n) is bounded both
(iii) Θ - Big theta notation

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.
Where t(n) and g(n) are nonnegative functions defined on the set of natural numbers.
Θ = Asymptotic tight bound = Useful for average case analysis

FIGURE 1.7 Big-theta notation: t (n) ∈ Θ(g(n)).

Prove the assertions 𝑛 (𝑛 − 1) ∈ Θ(𝑛2).

1

2
Example 5:

𝑛 (𝑛 − 1) = 1 𝑛2 − 1 𝑛 ≤ 1 𝑛2 for all
Proof: First prove the right inequality (the upper bound):
1

n ≥ 0.
2 2 2 2

𝑛 (𝑛 − 1) = 1 𝑛2 − 1 𝑛 ≥ 1 𝑛2 − [1 𝑛] [1 𝑛] for all n ≥ 2.
Second, we prove the left inequality (the lower bound):
1

2 2 2 2 2 2

± 1
𝑛 (𝑛 − 1 ) ≥ 1
𝑛2
 2 4
𝑛2 ≤ 1 𝑛 (𝑛 − 1) ≤ 1 𝑛2
1
1
Hence, 𝑛 (𝑛 − 1) ∈ Θ(𝑛2)
41
i.e.,
2 2 1

2 4 2
, where c2= , c1= and n0=2
Note: asymptotic notation can be thought of as "relational operators" for functions similar to the

= ⇒ Θ(), ≤ ⇒ O(), ≥ ⇒ Ω(), < ⇒ o(), > ⇒ ω()

corresponding relational operators for values.

Useful Property Involving the Asymptotic Notations

The following property, in particular, 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: The proof extends to orders of growth the following simple fact about four arbitrary real

Since t1(n) ∈ O(g1(n)), there exist some positive constant c1 and some nonnegative integer
numbers a1, b1, a2, b2: if a1 ≤ b1 and a2 ≤ b2, then a1 + a2 ≤ 2 max{b1, b2}.

n1 such that

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

t1(n) ≤ c1g1(n) for all n ≥ n1.

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

Let us denote c3 = max{c1, c2} and consider n ≥ max{n1, n2} so that we can use
both inequalities. Adding them yields the following:
t1(n) + t2(n) ≤ c1g1(n) + c2g2(n)
≤ c3g1(n) + c3g2(n)
= c3[g1(n) + g2(n)]
≤ c32 max{g1(n), g2(n)}.

Hence, t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}), with the constants c and n0 required by the
definition O being 2c3 = 2 max{c1, c2} and max{n1, n2}, respectively.
The property implies that the algorithm’s overall efficiency will be determined by the part
with a higher order of growth, i.e., its least efficient part.
± t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)), then t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}).

Basic rules of sum manipulation

Summation formulas

MATHEMATICAL ANALYSIS FOR 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 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.

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. (ND 2015)
ALGORITHM F(n)
//Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n!
if n = 0 return 1
else return F(n − 1) * n

Algorithm analysis
 For simplicity, we consider n itself as an indicator of this algorithm’s input size. i.e. 1.
 The basic operation of the algorithm is multiplication, whose number of executions we
denote 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) = M(n-1) + 1 for n > 0

To compute To multiply
F(n-1) F(n-1) by n
 M(n − 1) multiplications are spent to compute F(n − 1), and one more multiplication is
needed to multiply the result by n.

Recurrence relations
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,

Solve the recurrence relation (𝑛) = (𝑛 − 1) + 1, i.e., to find an explicit formula for
namely n − 1. Such equations are called recurrence relations or recurrences.

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. First, 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. Second, by inspecting the
pseudocode’s exiting line, we can see that when n = 0, the algorithm performs no multiplications.

Thus, 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 for n = 0.

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
…
= M(n − i) + i
…
= M(n − n) + n
= n.
Therefore M(n)=n

MATHEMATICAL ANALYSIS FOR NON-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 basic operation (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 least, establish its order of growth.

EXAMPLE 1: Consider the problem of finding the value of the largest element in a list of n
numbers. Assume that the list is implemented as an array for simplicity.
ALGORITHM MaxElement(A[0..n − 1])
//Determines the value of the largest element in a given array
//Input: An array A[0..n − 1] of real numbers
//Output: The value of the largest element in A
maxval ←A[0]
for i ←1 to n − 1 do
if A[i]>maxval
maxval←A[i]
return maxval

Algorithm analysis
 The measure of an input’s size here is the number of elements in the array, i.e., n.
 There are two operations in the for loop’s body:
o The comparison A[i]> maxval and
o The assignment maxval←A[i].

 The comparison operation is considered as the algorithm’s basic operation, because the
comparison is executed on each repetition of the loop and not the assignment.
 The number of comparisons will be the same for all arrays of size n; therefore, there is no
need to distinguish among the worst, average, and best cases here.
 Let C(n) denotes the number of times this comparison is executed. 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, the sum for C(n) is
calculated as follows:
𝑛−

𝑐(𝑛) = ∑
=
i.e., Sum up 1 in repeated n-1 times
𝑛−

𝑐(𝑛) = ∑ = 𝑛 − ∈ ()
=

EXAMPLE 2: Consider the element uniqueness problem: check whether all the Elements in a
given array of n elements are distinct.
ALGORITHM UniqueElements(A[0..n − 1])
//Determines whether all the elements in a given array are distinct
//Input: An array A[0..n − 1]
//Output: Returns “true” if all the elements in A are distinct and “false” otherwise
for i ←0 to n − 2 do
for j ←i + 1 to n − 1 do
if A[i]= A[j ] return false
return true
Algorithm analysis
 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.
 One comparison is made for each repetition of the innermost loop, i.e., for each value of the
loop variable j between its limits i + 1 and n − 1; this is repeated for each value of the outer
loop, i.e., for each value of the loop variable i between its limits 0 and n − 2.

EXAMPLE 3: Consider matrix multiplication. 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, j ≤ n − 1.