DESIGN AND ANALYSIS OF

ALGORITHMS
UNIT I INTRODUCTION 9
Notion of an Algorithm
– Fundamentals of Algorithmic Problem Solving
– Important Problem Types
– Fundamentals of the Analysis of Algorithm
Efficiency
– Analysis Framework
– Asymptotic Notations and its properties
– Mathematical analysis for Recursive and Non-
recursive algorithms.
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.

•
• 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.
 Odd or Even
ALGORITHM Eventest(val)
//This algorithm test whether given number is
odd or even
//Input:the number to be tested i.e.val
//Output:Appropriate messages indicating even or odd
If(val%2==0)then
write(“Given number is even”)
Else
write(“Given number is odd”)
 Pseudo-Code Conventions:

1. Comments begin with // and continue until the end of line.

2. Blocks are indicated with matching braces {and}.
3. An identifier begins with a letter. The data types of variables are not
explicitly declared.
4 Compound data types can be formed with records. Here is an example,
Node. Record
{
data type – 1 data-1;
.
.
data type – n data – n; node * link;
}
• Here link is a pointer to the record type node. Individual data items of a
record can be accessed with -> and period.
•
5 Assignment of values to variables is done using the assignment statement.
• <Variable>:= <expression>;

6)There are two Boolean values TRUE and FALSE.

– à Logical Operators AND, OR, NOT

– àRelational Operators <, <=,>,>=, =, !=

7) The following looping statements are employed.

For, while and repeat-until

While Loop:
While < condition > do
{
<statement-1>
..
.

<statement-n>
}
For Loop:
For variable: = value-1 to value-2 step step do

{
<statement-1>
.
.
.
<statement-n>
}
repeat-until:

repeat
<statement-1>
.
.
.
<statement-n>
until<condition>
8.A conditional statement has the following forms.

à If <condition> then <statement>

à If <condition> then <statement-1> Else <statement-1>

Case statement:
Case
{

}
<condition-1> : <statement-1>
.
.
.
: <condition-n> : <statement-n>
: else : <statement-n+1>
}
9.Input and output are done using the instructions read & write.

10.There is only one type of procedure: Algorithm, the heading takes the form,

Algorithm Name (Parameter lists)

à As an example, the following algorithm fields & returns the maximum of ‘n’ given
numbers:

algorithm Max(A,n)
// A is an array of size n
.{
Result := A[1];
for I:= 2 to n do
if A[I] > Result then
Result :=A[I];
return Result;
}
In this algorithm (named Max), A & n are procedure parameters. Result & I are Local variables.
 Factorial of n number
Algorithm fact(n)
//problem description:This algorithm finds the factorial
of a given number n
//Input: the number n of the factorial is to be calculated
//output: factorial value of given n number
if(n 1)then
return 1
else
return n*fact(n-1)
 Multiplication of two matrics
Algorithm Mul(A,B,n)
For i<--1 to n do
For j<--1 to n do
C[i,j]<--0
For k<--1 to n do
C[I,j]c[i,j]+A[i,k]B[k,j]
• Steps for writing an algorithm:
• An algorithm is a procedure. It has two parts; the first part is head and the second part is
body.
• The Head section consists of keyword Algorithm and Name of the algorithm with
parameter list. E.g. Algorithm name1(p1, p2,…,p3)
The head section also has the following:
//Problem Description:
//Input:
//Output:
• In the body of an algorithm various programming constructs like if, for, while and some
statements like assignments are used.
• The compound statements may be enclosed with { and } brackets. if, for, while can be closed
by endif, endfor, endwhile respectively. Proper indention is must for block.
• Comments are written using // at the beginning.
• The identifier should begin by a letter and not by digit. It contains alpha numeric letters after
first letter. No need to mention data types.
• The left arrow “←” used as assignment operator. E.g. v←10
• Boolean operators (TRUE, FALSE), Logical operators (AND, OR, NOT) and Relational
operators (<,<=, >, >=,=, ≠, <>) are also used.
• Input and Output can be done using read and write.
• Array[], if then else condition, branch and loop can be also used in algorithm
• 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
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.
• 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.
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 p m and p times in m
and n, respectively, it should be repeated min{p m , p n n } 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.
•
• As an example, consider the application of the algorithm to finding the
list of prime’s not exceeding n=25:
• 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Fundamentals of Algorithmic Problem Solving
• 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.
•
• 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. E.g., extracting square
roots, solving nonlinear equations, and evaluating
definite integrals.
• 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 = Programs

–· 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.
•
• Methods of Specifying an Algorithm
• There are three ways to specify an algorithm.
They are:
Natural language
Pseudocode
Flowchart
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

• Step 1: Read the first number, say a.
• Step 2: Read the first number, say b.
• Step 3: Add the above two numbers and store the result in c.
• Step 4: Display the result from c.

Such a specification creates difficulty while actually implementing it.

Hence many programmers prefer to have specification of algorithm by means
of Pseudocode.
• Pseudocode
– Pseudocode is a mixture of a natural language and programming
language 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.

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

1. Sorting
2. Searching
3. String processing
4. Graph problems
5. Combinatorial problems
6. Geometric problems
7. Numerical problems
• 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.
• 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.
• 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
•
• 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.
• 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.
• 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.
•
• 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.
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
•
• 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.
•
• 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.
Problem Statement Input Size Basic Operation

Searching a key element List of n elements Comparison of key with

from the list of n elements every element of list

Performing matrix The two matrics with n * n Actual multiplication of the

multiplication elements in the matrices

Computing GCD of two Two numbers Division

numbers
• Then we compute the total number of time
taken by the basic operation
• Computer the running time of basic operation
can be obtained following formula
• T(n)~Cop C(n)
• T(n)--Running time of basic operation
• Cop time taken by the basic operation to
execute
• C(n) Number of times the oepration needs
to be executed
• 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

Very big
104 102 13 104 1.3•105 108 1012 computation

105 3.2•102 17 105 1.7•106 1010 1015

106 103 20 106 2.0•107 1012 1018

• The logarithmic function is slowest function.
• Exponential function 2n is fastest and grows
rapidly with varying input size n.
• The exponential function gives huge values for
small input n
• N=16
• 2n=65536
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
• The probability of a successful search is equal to p (0 ≤ p ≤ 1) and
• 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
 Mathematical analysis for recursive
algorithm
• 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.
• Recursive Evaluation of n!
• Definition: n! = 1 * 2 * ... *(n-1) * n for n 1 and
0! = 1
• Recursive definition of n! : F(n) = F(n-1)*n for
n >= 1 and F(0) = 1
• 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
• Step1 : the factorial algorithm works for input size n
• Step2:the basic operation in computing factorial is multiplication
• Step 3: the recurive function cal can be formulated as
• F(n)=F(n-1)*n where n>0
• The basic operation multiplication is given as M(n).
• And M(n)is multiplication count to compute factorial (n)

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

• M(n − 1) ---these multiplications are required to compute

factorial(n-1)
• 1---- to multiply F(n-1) by n
• Forward Substitution :
M(1)=M(0)+1
M(2)=M(1)+1=1+1=2
M(3)=M(2)+1=2+1=3
Backward Substitution
M(n)= M(n − 1) +1
M(n-1) = M(n-2) + 1;
M(n-2) = M(n-3)+1

• M(n) = [M(n-2)+1] + 1
= M(n-2) + 2
= [M(n-3)+1+2]
= M(n-3) + 3
=M(n-n) + n
=n
General Formula
M(n)=M(n-i)+i

time Complexity: O(n)

 Tower of Hanoi
• Tower of Hanoi is a mathematical puzzle where we
have three rods (A, B, and C) and N disks.
• Initially, all the disks are stacked in decreasing value of
diameter
• i.e., the smallest disk is placed on the top and they are
on rod A.
• The objective of the puzzle is to move the entire stack
to another rod (here considered C), obeying the
following simple rules:
•
• RULES:
• Only one disk can be moved at a time.
• Each move consists of taking the upper disk
from one of the stacks and placing it on top of
another stack
• i.e. a disk can only be moved if it is the
uppermost disk on a stack.
• No disk may be placed on top of a smaller
disk.
• Tower of Hanoi using Recursion:
• The idea is to use the helper node to reach the
destination using recursion. Below is the
pattern for this problem:
• Shift ‘N-1’ disks from ‘A’ to ‘B’, using C.
• Shift last disk from ‘A’ to ‘C’.
• Shift ‘N-1’ disks from ‘B’ to ‘C’, using A.
•
• Move disk 1 from rod A to rod C
• Move disk 2 from rod A to rod B
• Move disk 1 from rod C to rod B
• Move disk 3 from rod A to rod C
• Move disk 1 from rod B to rod A
• Move disk 2 from rod B to rod C
• Move disk 1 from rod A to rod C
ALGORITHM TOH(n,A,B,C)
{
If(n=1)then
{
Write(“the disk moved from A to C”);
Return
}
Else
{
//move top n-1 disks from A to B using C
TOH(n-1,A,B,C);
//move remaining disk from B to C using A
TOH(n-1,B,C,A);
}
}
• Mathematical Analysis
Step1: The input size is n – total number of disk
Step2: the basic operation in the problem is moving disks
from one rod to another
• When n>1,then to move these disks from A to C using B
• We move first recurisvely n-1 disks from A to B using
Auxillary C
• Then we move largest disk directly from A to C and
finally move n-1 disks from B to C
• If n=1, move A to C
Step 3 : the moves of disks are denoted by M(n)
• M(n )depends on number of disks n
• The recurrence relation can then set up as
• M(1)=1 only 1 move needed(1,.,.,.,)
• If n>1 then need two recursive calls plus one
move
• M(n)=M(n-1)+1+M(n-1)
• M(n-1) ----move n-1 disk from A to B
• 1---to move largest disk from A to C
• M(n-1) ---move n-1 disks from B to C
• General formula
• M(n)=2M(n-1)+1
• Step 4 :
• Solving recurrence M(n)=2M(n-1)+1 using two
substitution methods
• Forward Substitution:
• For n>1
• M(2)=2M(1)+1= 3
• M(3)=2M(2)+1= 2(3)+1=7
• M(4)=15
 Mathematical analysis for Non recursive
algorithm
• 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 sum for the number of times the basic operation is
executed.
5. simplify the sum using standard formula and rules
Finding the Element with maximum value in a given array
Algorithm
//This algorithm is for finding the maximum value element
from the array
//array A[0…. N-1]
// returs the largest element from array
Max_element(A[0…..n-1])
Max_value<---- A[0]
For i<---1 to n-1 do
{
If(A[i]>Max_value)then
Max_value<---A[1]
}
Return Max_value
• Step1 : input size n
• Step2 :the basic operation is comparison in loop for finding larger value
• Step 3: the comparison is executed on each repetition of the loop.As the
comparsion is made for each value of n there is no need to find
bestcase ,worst case,average case
• Step 4:
• Let c(n) be the number of times the comparsion is executed.
• The alorithm makes comparsion each time the loop executes.
• That means with each new value I the comparsion is made.
• Step 5
• Simply the sum
• C(n)=∑1
• C(n)=n-1 =Θ(n)
 CLOSEST-PAIR AND CONVEX-HULL PROBLEMS

• straight forward approach (Brute Force) to

two well-known problems dealing with a finite
set of points in the plane.
• These problems are very useful in important
applied areas like computational geometry
and operations research.
• Closest-Pair Problem
• The closest-pair problem finds the two closest points in a set of
n points.
• It is the simplest of a variety of problems in computational
geometry that deals with proximity of points in the plane or
higher-dimensional spaces.
• Consider the two-dimensional case of the closest-pair problem.
• The points are specified in a standard fashion by their (x, y)
Cartesian coordinates and that the distance between two points
pi(xi, yi) and pj(xj, yj ) is the standard Euclidean distance.
• 𝑑(𝑝i , 𝑝j) = √(xi − xj)2 + (yi − yj)2
• The following algorithm computes the distance between each
pair of distinct points and finds a pair with the smallest
distance.
• ALGORITHM BruteForceClosestPair(P)
• //Finds distance between two closest points in the plane by
brute force
• //Input: A list P of n (n ≥ 2) points p1(x1, y1), . . . , pn(xn, yn)
• //Output: The distance between the closest pair of points
• d←∞
• for i ←1 to n − 1 do
• for j ←i + 1 to n do
• d ←min(d, sqrt((xi− xj )2 + (yi− yj )2)) //sqrt is square root
• return d
Convex-Hull Problem Convex Set
• A set of points (finite or infinite) in the plane is
called convex
• if for any two points p and q in the set, the
entire line segment with the endpoints at p
and q belongs to the set.
• (a) Convex sets
• Sets that are not convex.
• Convex hull
• The convex hull of a set S of points is the smallest
convex set containing S. (The smallest convex hull of S
must be a subset of any convex set containing S.)
• If S is convex, its convex hull is obviously S itself.
• If S is a set of two points, its convex hull is the line
segment connecting these points. If S is a set of three
points not on the same line, its convex hull is the
triangle with the vertices at the three points given;
• if the three points do lie on the same line, the convex
hull is the line segment with its endpoints at the two
points that are farthest apart
• The convex-hull problem is the problem of constructing
the convex hull for a given set S of n points.
• To solve it, we need to find the points that will serve as
the vertices of the polygon in question.
• Mathematicians call the vertices of such a polygon
“extreme points.”
• By definition, an extreme point of a convex set is a point
of this set that is not a middle point of any line segment
with endpoints in the set.
• For example, the extreme points of a triangle are its three
vertices, the extreme points of a circle are all the points of
its circumference, and the extreme points of the convex
hull of the set of eight points in Figure 2.3 are p1, p5, p6,
p7, and p3.
• A few elementary facts from analytical geometry are needed to
implement the above algorithm.
• First, the straight line through two points (x1, y1), (x2, y2) in the
coordinate plane can be defined by the equation ax + by =
c,where a = y2 − y1, b = x1 − x2, c = x1y2 − y1x2.
• Second, such a line divides the plane into two half-planes: for
all the points in one of them, ax + by > c, while for all the
points in the other, ax + by < c. (For the points on the line itself,
of course, ax + by = c.) Thus, to check whether certain points
lie on the same side of the line, we can simply check whether
the expression ax + by − c has the same sign for each of these
points
Convex Hull