Course Instructor

ANUJ GHIMIRE
 Chapter 4

Recurrence Relation and

Algorithmic Analysis
Recurrence Relation
 Consider the following:
a) Start with number 5
b) Given any term , add 3 to get next term
If we list the term using above rule then we obtain,
5, 8, 11, 14, 17, ……………..……(i)
If we denote eqn (i) as a0, a1, a2, a3, ………..…..an,
We may rephrase above instruction as:
an = an – 1 + 3 ; with initial condition, a0 = 5, n≥1

Recurrence Relation
Recurrence Relation
 The sequence a0 , a1 , a2……….,an is a recurrence
relation that relates an to certain of its predecessors a0,
a1,……....,an-1.
 If a sequence can be expressed by an equation in terms
of previous element then it is called the Recurrence
Relation.
 Initial conditions for the sequence a0 , a1 , a2……….,an
are explicitly given values for a finite no. of terms of
the sequence.
Recurrence Relation
 For Example:
 Fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 and so on.
 The recurrence relation for Fibonacci sequence is
fn=fn-1+fn-2, n  2

Recurrence Relation

and initial conditions fo=0, f1=1

fo f1 f2 f3 f4 f5 f6
0 1 2 3 5 8 13
Recurrence Relation
 Tower of Hanoi Problem
Peg 1 (Source) Peg 2 (Auxiliary) Peg 3 (Destination)

Tower of Hanoi, is a mathematical puzzle which consists of three

towers (pegs) and more than one disks of different diameter is mounted
in peg 1 as shown in the above figure.
Recurrence Relation
 These disks are of different diameter and stacked
upon in an ascending order, i.e. the disk with
smaller diameter sits over the disk with larger
diameter.
 There are other variations of the puzzle where the
number of disks increase, but the tower count
remains the same.
 The mission is to move all the disks from peg 1 to
peg 3 without violating the sequence of
arrangement.
Recurrence Relation
 A few rules to be followed for Tower of Hanoi puzzle
are:
 Only one disk can be moved among the towers at
any given time.
 Only the "top" disk can be removed.
 No large disk can sit over a small disk.
 We can have one and only extra peg other than
source and destination
Recurrence Relation
 Tower of Hanoi puzzle with three disks can be solved
as:
Peg 1 Peg 2 Peg 3
Recurrence Relation
Move 1
Recurrence Relation
Move 2
Recurrence Relation
Move 3
Recurrence Relation
Move 4
Recurrence Relation
Move 5
Recurrence Relation
Move 6
Recurrence Relation
Move 7
Recurrence Relation
Steps Completed!
Peg 1 Peg 2 Peg 3

Done moving n = 3 disks from peg 1 (Source) to peg 3 (Destination).

Total no. of moves required = 7
 Recurrence Relation
Let n denote the total no. of disks mounted on peg 1 (Source).
Let Cn denote the total no. of moves required to transfer n
disks from peg 1 (Source) to peg 2 (Destination) is:
Cn = 2n – 1, n>1
For 1 disk, C1 = 1
For 2 disk, C2 = 3
For 3 disk, C3 = 7 and so on.
The recurrence relation for the sequence C1,C2,…..,Cn, where Cn
denotes no. of moves in Tower of Hanoi puzzle is given as:
Cn = 2Cn-1 + 1 , n>1
with initial condition C1 = 1
Recurrence Relation
A customer deposits 10,000 in a bank and he
gets 11% interest per annual and the interest
amount is accumulated every year.
Find the recurrence relation to compute total
amount customer receive after 10 year.
And also calculate amount that customer
receive after 30 years.
Solving Recurrence Relation
 To solve a recurrence relation having the sequence
a0, a1, a2, …….,an
 We need to find an explicit formula for the general
term an.
 The equation that satisfies the recurrence relation is
called solution of recurrence relation.
 We will focus on two to solve the recurrence relation:
 Solution of Recurrence relations by iterations
 Special method that applies to linear homogeneous
recurrence relations with constant coefficients.
Solving Recurrence Relation Using Iteration
Example 1: Solve an = an-1 + 3 by iteration with
initial condition a1 = 2.
Solution:
We have, an = an-1 + 3 ……….(i)
Replacing n by n-1, we get,
an-1 = an-2 + 3
Substituting the value of an-1 in equation (i), we get,
an = an-2 + 2*3 ……….(ii)
Again, Replacing n by n-2, in equation (i), we get,
an-2 = an-3 + 3
 Solving Recurrence Relation Using Iteration
Again, Replacing n by n-2, in equation (i), we get,
an-2 = an-3 + 3
Similarly, Substituting the value of an-2 in equation (ii), we
get,
an = an-2 + 3*3
In general,
an = an-k + k*3
If k = n-1,
an = a1 + (n-1)*3
Which is the required solution for the given Recurrence
Relation.
Solving Recurrence Relation Using Iteration
So, a10 = a1 + (10-1)*3
= a1 + 9*3
= 2+27
= 29
Solving Recurrence Relation Using Iteration
Example 2: Solve the recurrence relation, Sn = 2Sn-1
by iteration with initial condition S0 = 1.

Solution:
We have, Sn = 2Sn-1 …………….(i)
Replacing n by n-1, we get,
Sn-1 = 2Sn-2
Substituting the value of Sn-1 in equation (i), we get,
Sn = 2*2 Sn-2 ……….(ii)
Replacing n by n-2, in equation (i), we get,
Sn-2 = 2Sn-3
 Solving Recurrence Relation Using Iteration
Replacing n by n-2, in equation (i), we get,
Sn-2 = 2Sn-3
Substituting the value of Sn-2 in equation (ii), we get,
Sn = 2*2*2 Sn-3
In general,
Sn = 2k Sn-k
If k = n,
Sn = 2n S 0
Which is the required solution for the given Recurrence
Relation.
Solving Recurrence Relation Using Iteration
Example 3: Find the solution of Tower of Hanoi
Puzzle using the recurrence relation
 Let, Hn be the total moves required to move n disk
from peg 1 to peg 3.
 First with the help of peg 2 & peg 3, move (n-1) disks
from peg 1 to peg 2. This requires, Hn-1 moves
 Then, largest disk from peg 1 is moved to peg 3, which
requires 1 move.
 Finally, (n-1) disks of peg 2 are moved to peg 3 with the
help of peg 1 & peg 2.
Solving Recurrence Relation Using Iteration
 This requires further Hn-1 moves.
 Hence, We can define a recurrence relation as:
Hn = Hn-1 + 1 + Hn-1
= 2Hn-1 + 1
Now,
Hn = 2Hn-1 +1
=2[2Hn-2 +1] + 1
=22Hn-2 + 2 + 1
=22[2Hn-3 +1] + 2 + 1
Solving Recurrence Relation Using Iteration
=23Hn-3 + 22 + 21 + 20
.
.
.
=2n-1H1 + 2n-2 +…………..+ 22 + 21 + 2
=2n-1 + 2n-2 +…………..+ 22 + 21 + 20 [since H1=1]
This is a Geometric series with common ratio(r)
= 2n-1 /2n-2
=2
Solving Recurrence Relation Using Iteration
The sum can be calculated as,
Sn = 𝑎[𝑟𝑛 −1]/ (𝑟−1)
= 1[2𝑛 −1]/(2−1) [a is first term of series so 1]

Sn = 2n -1.
This is s the required solution of Tower of Hanoi.
 Linear Homogeneous Recurrence
Relation
 A linear homogeneous recurrence relation of order k
with constant coefficients is a recurrence relation of
the form:
an = c1an-1 + c2an-2 + c3 an-3 + … … + ck an-k, ck ≠ 0
 Notice that a linear homogeneous recurrence relation
of order k with constant coefficients with the k initial
conditions
a0 = c0, a1 = c1, …....,ak-1 = ck-1 uniquely defines a sequence.
 Linear Homogeneous Recurrence
Relation
 To calculate the solution of the linear homogeneous
recurrence relation we need the find the equation that
satisfies the recurrence relation.
 Let an= rn be the equation that satisfies the recurrence
relation then
an = c1an-1 + c2an-2 + c3 an-3 + … … + ck an-k ……….(1)
can be written as:
rn= c1rn-1 + c2rn-2 + c3 rn-3 + … … + ck rn-k…….…….(2)
 Linear Homogeneous Recurrence
Relation
 Dividing both side by rn-k of (2) we get
rk= c1rk-1 + c2rk-2 + c3rk-3 + … … + ck
or rk- c1rk-1 - c2rk-2 - c3rk-3 - … … - ck = 0 …….…….(3)
 This equation (3) is called as characteristics equation
of the given recurrence relation.
 The roots of these equation are called characteristics
roots and are used to give the explicit formula for all
the solution of recurrence relation.
 Solution of Linear Homogeneous
Recurrence Relation
 A linear homogeneous recurrence relation of order k with
constant coefficients is a recurrence relation of the form:
an = c1an-1 + c2an-2 + c3 an-3 + … … + ck an-k, ck ≠ 0
 To calculate the solution of the linear homogeneous
recurrence relation we need the find the equation that
satisfies the recurrence relation.
 Let an= rn be the equation that satisfies the recurrence relation
then
an = c1an-1 + c2an-2 + c3 an-3 + … … + ck an-k ……….(1)
can be written as:
rn= c1rn-1 + c2rn-2 + c3 rn-3 + … … + ck rn-k…….…….(2)
 Solution of Linear Homogeneous
Recurrence Relation
 Dividing both side by rn-k of (2) we get
rk= c1rk-1 + c2rk-2 + c3rk-3 + … … + ck
or rk- c1rk-1 - c2rk-2 - c3rk-3 - … … - ck = 0 …….…….(3)
 Solution of Linear Homogeneous
Recurrence Relation
Find the characteristic equation and roots of the
given recurrence relation.
an = 5an-1 - 6an-2
Solution:
Given recurrence relation is an = 5an-1 - 6an-2 …………(1)
Let, the solution be an =rn
Then this solution must satisfy above recurrence relation.
So, eqn (1) can be written as:
 Solution of Linear Homogeneous
Recurrence Relation
rn = 5rn -1 - 6rn-2
Dividing Both sides by rn-2 we get,
rn/rn−2 = 5rn−1/rn−2 − 6rn−2/rn−2
or r2 = 5r – 6
or r2 - 5r + 6 = 0………….(2)
eqn (2) is the characteristic equation of the given
recurrence relation.
On solving this equation we get, r=2 and 3 which are its
characteristic roots.
 Solution of Linear Homogeneous
Recurrence Relation
Find the characteristic equation and roots of the
given recurrence relation.
an = 6an-1 - 9an-2
Solution:
Given recurrence relation is an = 6an-1 - 9an-2 …………(1)
Let, the solution be an =rn
Then this solution must satisfy above recurrence relation.
So, eqn (1) can be written as:
 Solution of Linear Homogeneous
Recurrence Relation
rn = 6rn -1 - 9rn-2
Dividing Both sides by rn-2 we get,
rn/rn−2 = 6rn−1/rn−2 − 9rn−2/rn−2
or r2 = 6r – 9
or r2 - 6r + 9 = 0………….(2)
eqn (2) is the characteristic equation of the given
recurrence relation.
On solving this equation we get, r=3 and 3 which are its
characteristic roots.
 Solution of Linear Homogeneous
Recurrence Relation
THEOREM 1:
Let, an = c1an-1 + c2an-2 be the linear homogeneous
recurrence relation of degree 2 and its characteristics
equation is:
r2 - c1r - c2 = 0 ………….(1)
This characteristics equation have two possible roots say
r1 and r2
The value of roots can have two cases:
 Solution of Linear Homogeneous
Recurrence Relation
Case-I: If r1 and r2 are distinct roots of the characteristics
equation then, the solution is of the form,
an = 𝜶𝟏𝒓𝟏𝒏 + 𝜶𝟐𝒓𝟐𝒏
Case-II: If If r1 and r2 are equal roots of the
characteristics equation then, the solution is of the form,
an = 𝜶𝟏𝒓𝒏 + 𝒏𝜶𝟐𝒓𝒏
where 𝜶𝟏 and 𝜶𝟐 are the constants.
 Solution of Linear Homogeneous
Recurrence Relation
What is the solution of the recurrence relation :
an = 5an-1 – 6an-2 with a0=3, a1=5.
Solution:
Given recurrence relation: an = 5an-1 – 6an-2 ----------------(i)
The characteristics equation is,
r2 - 5r + 6 = 0 ………………….(ii)
r2 – 3r – 2r + 6 =0
r(r – 3) -2(r-3) = 0
(r – 2)(r – 3) = 0
r1=2 and r2=3
Here the roots are distinct and real.
 Solution of Linear Homogeneous
Recurrence Relation
Since, roots are distinct and real the solution is in the
form:
an = 𝜶𝟏𝒓𝟏𝒏 + 𝜶𝟐𝒓𝟐𝒏
or an = 𝜶𝟏 *2𝒏 + 𝜶𝟐 *3𝒏 …………….(iii)
Now, applying initial condition i.e. a0 = 3 and a1 = 5
when n = 0, eqn (iii) becomes
a0 = 𝜶𝟏 *20 + 𝜶𝟐 *30
3= 𝜶𝟏 + 𝜶𝟐 ---------------(iv)
when n = 1, eqn (iii) becomes
a1 = 𝜶𝟏 *21 + 𝜶𝟐 *31
5= 2𝜶𝟏 + 3𝜶𝟐 ---------------(v)
 Solution of Linear Homogeneous
Recurrence Relation
Solving equation (iv) and (v),
we get, 𝛼1 = 4 𝑎𝑛𝑑 𝛼2 = -1
Substituting the value of 𝛼1 = 4 𝑎𝑛𝑑 𝛼2 = -1 in eqn (iii), we
get
an = 4*2n – 1*3n
which is the required solution.
 Solution of Linear Homogeneous
Recurrence Relation
What is the solution of the recurrence relation :
an= 6an-1 – 9an-2 with a0=5, a1=7.
Solution:
Given recurrence relation: an = 6an-1 – 9an-2 ----------------(i)
The characteristics equation is,
r2 - 6r + 9 = 0 ………………….(ii)
r2 – 3r – 3r + 9 =0
r(r – 3) -3(r-3) = 0
(r – 3)(r – 3) = 0
r1=3 and r2=3
Here the roots are same and real.
 Solution of Linear Homogeneous
Recurrence Relation
Since, roots are same and real the solution is in the form:
an = 𝜶𝟏𝒓𝟏𝒏 + n𝜶𝟐𝒓𝟐𝒏
or an = 𝜶𝟏 *3𝒏 + n𝜶𝟐 *3𝒏 …………….(iii)
Now, applying initial condition i.e. a0 = 5 and a1 = 7
when n = 0, eqn (iii) becomes
a0 = 𝜶𝟏 *30 + n𝜶𝟐 *30
5= 𝜶𝟏 ---------------(iv)
when n = 1, eqn (iii) becomes
a1 = 𝜶𝟏 *31 + n𝜶𝟐 *31
7= 3𝜶𝟏 + 3𝜶𝟐 ---------------(v)
 Solution of Linear Homogeneous
Recurrence Relation
Substituting 𝛼1 = 5 in eqn (v),
we get, 𝛼2 = - 8/3
Substituting the value of 𝛼1 = 5 𝑎𝑛𝑑 𝛼2 = - 8/3 in eqn (iii),
we get
an = 5*3n – 8/3*n*3n
which is the required solution.
 Solution of Linear Homogeneous
Recurrence Relation
Derive an Explicit Formula For Fibonacci series.
Solution:
The recurrence relation for Fibonacci series is given by:
an = an-1 + an-2 ----------------(i)
with initial condition a0=0 and a1 = 1
The characteristics equation is,
r2 - r - 1 = 0
The characteristics roots are:
−𝑏± 𝑏2 −4𝑎𝑐
r=
2𝑎
 Solution of Linear Homogeneous
Recurrence Relation
1± 5
r= so,
2
1+ 5 1− 5
r1 = and r2 =
2 2
Since, roots are distinct and real the solution is in the
form:
an = 𝜶𝟏 *r1𝒏 + 𝜶𝟐 *r2𝒏
1+ 5 𝒏 1− 5 𝒏
or an = 𝜶𝟏 2 + 𝜶𝟐 2 …………….(iii)
 Solution of Linear Homogeneous
Recurrence Relation
Now, applying initial condition i.e. a0 = 0 and a1 = 1
when n = 0, eqn (iii) becomes
1+ 5 0 1− 5 0
a0 = 𝜶𝟏 2 + 𝜶𝟐 2
0 = 𝜶𝟏 + 𝜶𝟐 -----------------------------(iv)
when n = 1, eqn (iii) becomes
1+ 5 1 1− 5 1
a1 = 𝜶𝟏 2 + 𝜶𝟐 2
1+ 5 1− 5
1= 𝜶𝟏 2 + 𝜶𝟐 2 ---------------(v)
 Solution of Linear Homogeneous
Recurrence Relation
Solving equation (iv) and (v),
1 1
we get, 𝛼1 = and 𝛼2 = -
5 5
1 1
Substituting the value of 𝛼1 = and 𝛼2 = - in eqn (iii),
5 5
we get
1 1+ 5 𝒏 1 1− 5 𝒏
an = -
5 2 5 2

which is the required solution.

 Solution of Linear Homogeneous
Recurrence Relation
THEOREM 2
Let, an = c1an-1 + c2an-2 + c3an-3 be the linear homogeneous
recurrence relation of degree 3 and its characteristics
equation is:
r3 - c1r2 – c2r – c3 = 0
If all roots are distinct then, the solution is of the form,
an = 𝜶𝟏𝒓𝟏𝒏 + 𝜶𝟐𝒓𝟐𝒏 + 𝜶𝟑𝒓𝟑𝒏
If two roots are equal then, the solution is of the form,
an = [𝜶𝟏 + 𝒏𝜶𝟐 ] 𝒓𝟏𝒏 + 𝜶𝟑𝒓𝟐𝒏
 Solution of Linear Homogeneous
Recurrence Relation
If all the roots are same , then the solution is of the form
an = [𝜶𝟏 + 𝒏𝜶𝟐 + 𝐧𝟐𝜶𝟑 ]𝒓n
 Solution of Linear Homogeneous
Recurrence Relation
What is the solution of the recurrence relation
an = 6an-1 – 11an-2 + 6an-3 with a0=2, a1=5 , a2=15.
Solution: Given recurrence relation:
an = 6an-1 – 11an-2 + 6an-3 ----------------(i)
The characteristics equation is:
r3 - 6r2 + 11r - 6 = 0
On solving above equation,
we get, r1=1, r2=2 , r3=3
Since all the roots are distinct.
 Solution of Linear Homogeneous
Recurrence Relation
The solution is in the form:
an = 𝜶𝟏𝒓𝟏𝒏 + 𝜶𝟐𝒓𝟐𝒏 + 𝜶𝟑𝒓𝟑𝒏
an = 𝜶𝟏*1𝒏 + 𝜶𝟐*2𝒏 + 𝜶𝟑*3𝒏 -----------------(ii)
Now, applying initial condition: a0=2, a1=5 , and a2=15.
when n = 0, eqn (ii) becomes
a0 = 𝜶𝟏*10 + 𝜶𝟐*20 + 𝜶𝟑*30
2 = 𝜶𝟏 + 𝜶𝟐 + 𝜶𝟑 -------------------(iii)
when n = 1, eqn (ii) becomes
a1 = 𝜶𝟏*11 + 𝜶𝟐*21 + 𝜶𝟑*31
5 = 𝜶𝟏 + 2𝜶𝟐 + 3𝜶𝟑 -------------------(iv)
 Solution of Linear Homogeneous
Recurrence Relation
when n = 2, eqn (ii) becomes
a2 = 𝜶𝟏*12 + 𝜶𝟐*22 + 𝜶𝟑*32
15 = 𝜶𝟏 + 4𝜶𝟐 + 9𝜶𝟑 -------------------(v)
Solving equation (iii) , (iv) and (v)
We get, 𝛼1 = 1 , 𝛼2 = −1 𝑎𝑛𝑑 𝛼3 = 2
Substituting the value of 𝛼1 = 1 , 𝛼2 = −1 𝑎𝑛𝑑 𝛼3 = 2 in
eqn (ii), we get
an = 1 − 𝟐𝒏 + 𝟐*𝟑𝒏
which is the required solution.
 Solution of Linear Homogeneous
Recurrence Relation
Q1. What is the solution of the recurrence relation
an - 3an-1 + 3an-2 - an-3 =0 with a0=1, a1=-2 , a2=-1.

Answer: an = 1 − 5*𝒏 +2𝒏2

Q2.What is the solution of the recurrence relation

an = 5an-1 - 7an-2 + 3an-3 with a0=1, a1=9 , a2=15.

Answer: an = [ 𝟑/𝟐 + 𝟗𝒏] − 𝟏/𝟐*𝟑n

 Solution of Linear Non-
Homogeneous Recurrence Relation
 A linear non-homogeneous recurrence relation of
order k with constant coefficients is a recurrence
relation of the form:
an = c1an-1 + c2an-2 + c3 an-3 + … … + ck an-k+ F(n) where
c1, c2 ,c3,……..ck are constant coefficient and ck ≠ 0
 Here an = c1an-1 + c2an-2 + c3an-3 + … … + ckan-k is called
associated homogeneous part and F(n) is called non-
homogeneous part.
 The solution of associated homogeneous part is called
General Solution (GS) and the solution of non-
homogenous part is called Particular Solution (PS).
 Solution of Linear Non-
Homogeneous Recurrence Relation
 The final solution of linear non-homogenous
recurrence relation is sum of General Solution and
Particular Solution.
an = an(GS) + an(PS)……………….(i)
where, an(GS): Solution of homogenous part
an(PS): Solution of non-homogenous part

 The method of computation an(GS) is similar to the

process to compute solution on linear homogeneous
recurrence relation.
 Solution of Linear Non-
Homogeneous Recurrence Relation
 In the equation of the following form:
an = c1an-1 + c2an-2 + c3 an-3 + … … + ck an-k+ F(n) where
c1, c2 ,c3,……..ck are constant coefficient and ck ≠ 0
 The F(n) i.e. the non-homogeneous part can be of
different form.
 The solution of non-homogeneous part i.e. particular
solution can be of different form depending on the nature
of F(n).
 Solution of Linear Non-
Homogeneous Recurrence Relation
 Case-I :
When F(n)= bn, and b is not the root of the characteristic
equation then particular solution is of the form:
an(PS) = Abn………….(1)
 Case-II :
When F(n)= bn, and b is the root of the characteristic
equation with multiplicity of m then particular solution is of
the form:
an(PS) = A*nm*bn……..……(2)
 Solution of Linear Non-
Homogeneous Recurrence Relation
 Case-III :
When F(n) is a polynomial in n.
If F(n) is first degree polynomial in n i.e.F(n)= n, then
particular solution is of the form:
an(PS) = An+B ..………….(3)
If F(n) is second degree polynomial in n2 i.e.F(n)= n2, then
particular solution is of the form:
an(PS) = An2 + Bn + C ..………….(4)
If F(n) is third degree polynomial in n3 i.e.F(n)= n3, then
particular solution is of the form:
an(PS) = An3 + Bn2 + Cn + D ..….….(5)
 Solution of Linear Non-
Homogeneous Recurrence Relation
 Case-IV :
When F(n) is a constant term. i.e.F(n)= k, where k is
constant
We can write F(n) = k.(I)n
If I is not the characteristic root then, particular solution is of
the form:
an(PS) = A ..………….(7)
If I is the characteristic root with multiplicity m then,
particular solution is of the form:
an(PS) = Anm ..………….(8)
 Solution of Linear Non-
Homogeneous Recurrence Relation
What is the solution of the recurrence relation
an - 2an-1 + an-2 = 7
Solution:
Given recurrence relation: an - 2an-1 + an-2 = 7………….(i)
The associated homogeneous part is,
an - 2an-1 + an-2 = 0
The characteristics equation is,
r2 - 2r + 1 = 0
r2 – r – r + 1 =0
r(r – 1) -r(r - 1) = 0
r1 = 1 , r2 = 1
 Solution of Linear Non-
Homogeneous Recurrence Relation
Since the roots are equal and real so, the general solution is in
the form:
an(GS) = 𝜶𝟏𝒓𝒏 + 𝒏𝜶𝟐𝒓𝒏
an(GS) = 𝜶𝟏1n + 𝒏𝜶𝟐 1n
an(GS) = 𝜶𝟏+ 𝒏𝜶𝟐 ……….…….(ii)
The non-homogeneous part is: an= 7
which can be written as an= 7(1)n
Here 1 is the characteristic root with multiplicity 2
So, the particular solution is in the form:
an(PS) = Anm
or an(PS) = An2 [Here m=2]
 Solution of Linear Non-
Homogeneous Recurrence Relation
Putting value of an in equation (i) we get,
An2 - 2A( n-1)2 + A(n-2)2 = 7
An2 - 2A( n2-2n+1) + A(n2-4n+4) = 7
A(n2 - 2n2 + 4n - 2 + n2- 4n + 4) = 7
A = 𝟕/𝟐
Hence the particular solution is: an(PS) = (7/2)n2
Total solution is:
an = an(GS) + an(PS)
an = 𝜶𝟏 + 𝒏𝜶𝟐 + (7/2)n2
which is the required solution.
 Solution of Linear Non-
Homogeneous Recurrence Relation
What is the solution of the recurrence relation :
an - 5an-1 + 6an-2 = 2 + n with initial condition a0 = 1 , a1 = 1.
Solution:
Given recurrence relation: an - 5an-1 + 6an-2 = 2 + n……………….(i)
The associated homogeneous part is,
an - 5an-1 + 6an-2 = 0
The characteristics equation is,
r2 - 5r + 6 = 0
r2 – 3r – 2r + 6 =0
r(r – 3) -2(r - 3) = 0
r1 = 2 , r2 = 3
 Solution of Linear Non-
Homogeneous Recurrence Relation
Since the roots are distinct and real so, the general solution is in
the form:
an(GS) = 𝜶𝟏𝒓1𝒏 + 𝜶𝟐𝒓2𝒏
an(GS) = 𝜶𝟏2n + 𝜶𝟐 3n……….…….(ii)

The non-homogeneous part is: an= 2+n

Here F(n) is polynomial in n, then the particular solution
is of the form:
an(PS) =An+B
 Solution of Linear Non-
Homogeneous Recurrence Relation
Substituting the value of an in equation (1) we get,
An + B – 5{A(n-1) + B { + 6{A(n-2) + B} = 2 + n
An+ B – 5{An - A + B } + 6{An - 2A + B} = 2 + n
An + B – 5An + 5A - 5B + 6An - 12A + 6B = 2 + n
2An – 7A + 2B = 2 + n..................(3)
Equating the coefficients we get,
2An=n...................(4)
-7A + 2B = 2.............(5)
 Solution of Linear Non-
Homogeneous Recurrence Relation
Solving equation (4) and (5) we get,
2A = 1
A=1/2
Again,
-7A + 2B = 2
0r -7(1/2) + 2B = 2
0r -7 + 4B = 4
or B = 11/4
On substituting the value of A and B the particular solution will
be
an(PS) =(1/2)n + 11/4
 Solution of Linear Non-
Homogeneous Recurrence Relation
Therefore the final solution is:
an = an(GS) + an(PS)
an = 𝜶𝟏2n + 𝜶𝟐 3n + (1/2)n + 11/4 …..……………(6)
To calculate 𝜶1 and 𝜶2 use initial condition a0 = 1 , a1 = 1 in
equation (6)
When n=0 equation (6) becomes
a0 = 𝜶𝟏20 + 𝜶𝟐 30 + (1/2)*0 + 11/4
1 = 𝜶𝟏 + 𝜶𝟐 + 11/4
𝜶𝟏 + 𝜶𝟐 = -7/4 ………………..(7)
 Solution of Linear Non-
Homogeneous Recurrence Relation
When n=1 equation (6) becomes
a1 = 𝜶𝟏21 + 𝜶𝟐 31 + (1/2)*1 + 11/4
1 = 2𝜶𝟏 + 3𝜶𝟐 + 1/2 + 11/4
2𝜶𝟏 + 3𝜶𝟐 = 1- ½ - 11/4
2𝜶𝟏 + 3𝜶𝟐 = - 9/4 ………………..(8)
Solving (7) and (8) we get,
𝜶1= -3 and 𝜶2=5/4
Putting the value of 𝜶1= -3 and 𝜶2=5/4 in equation (6) we get,
an = (-3)2n + (5/4)3n + (1/2)n + 11/4
which is the required solution.
 Solution of Linear Non-
Homogeneous Recurrence Relation
Solve the recurrence relation
an= 2an-1 + 8an-2 + 81n2
Solution:
Given recurrence relation: an= 2an-1 + 8an-2 + 81n2 ……………….(i)
The associated homogeneous part is,
an= 2an-1 + 8an-2
The characteristics equation is,
r2 - 2r - 8 = 0
r2 – 4r + 2r - 8 =0
r(r – 4) + 2(r - 4) = 0
r1 = 4 , r2 = -2
 Solution of Linear Non-
Homogeneous Recurrence Relation
Since the roots are distinct and real so, the general solution is in
the form:
an(GS) = 𝜶𝟏𝒓1𝒏 + 𝜶𝟐𝒓2𝒏
an(GS) = 𝜶𝟏 4n + 𝜶𝟐 (-2)n……….…….(ii)

The non-homogeneous part is: an= 81n2

Here F(n) is second degree polynomial in n, then the
particular solution is of the form:
an(PS) =An2 + Bn + C
 Solution of Linear Non-
Homogeneous Recurrence Relation
Substituting the value of an in equation (1) we get,
An2 + Bn + C= 2{A(n-1)2 + B(n-1) + C} + 8{A(n-2)2 + B(n-2) + C}
+ 81n2
Solving the above equation we get,
A=-9, B=-36 and C=-38
So, particular solution is
an(PS) = -9n2 - 36n - 38
Therefore the final solution is:
an = an(GS) + an(PS)
an = 𝜶𝟏 4n + 𝜶𝟐 (-2)n - 9n2 - 36n - 38
 Solution of Linear Non-
Homogeneous Recurrence Relation
Solve the recurrence relation
an= 5an-1 - 6an-2 + 7n
Solution:
Given recurrence relation: an= 5an-1 - 6an-2 + 7n ……………….(i)
The associated homogeneous part is,
an= 5an-1 - 6an-2
The characteristics equation is,
r2 - 5r + 6 = 0
r2 – 3r - 2r + 6 =0
r(r – 3) – 2(r - 3) = 0
r1 = 2 , r2 = 3
 Solution of Linear Non-
Homogeneous Recurrence Relation
Since the roots are distinct and real so, the general solution is in
the form:
an(GS) = 𝜶𝟏𝒓1𝒏 + 𝜶𝟐𝒓2𝒏
an(GS) = 𝜶𝟏 2n + 𝜶𝟐 3n……….…….(ii)

The non-homogeneous part is: an= 7n and 7 is not the

characteristics root.
So, the particular solution is of the form:
an(PS) =A7n
 Solution of Linear Non-
Homogeneous Recurrence Relation
Substituting the value of an in equation (1) we get,
A7n= 5 A7n-1 – 6 A7n-2 + 7n
Dividing both side by 7n we get,
A=(5/7)A – (6/49)A + 1
or 49A = 35A – 6A + 49
or A = 49/20
So, particular solution is
an(PS) = (49/20)7n
Therefore the final solution is:
an = an(GS) + an(PS)
an = 𝜶𝟏 2n + 𝜶𝟐 3n + (49/20)7n
 Solution of Linear Non-
Homogeneous Recurrence Relation
What is the solution of the recurrence relation :
an - 3an-1 + 2an-2 = 2n with a0 = 0 and a1 = 2.
Solution:
Given recurrence relation: an - 3an-1 + 2an-2 = 2n……….……(1)
The associated homogeneous part is,
an - 3an-1 + 2an-2 = 0
The characteristics equation,
r2 - 3r + 2 = 0
r2 – 2r – r + 2 =0
r(r – 2) -1(r-2) = 0
r1 = 1 , r2 = 2
 Solution of Linear Non-
Homogeneous Recurrence Relation
Since the roots are distinct and real so, the general solution is in
the form:
an(GS) = 𝜶𝟏𝒓1𝒏 + 𝜶𝟐𝒓2𝒏
an(GS) = 𝜶𝟏 1n + 𝜶𝟐 2n……….…….(2)

The non-homogeneous part is: an= 2n

Here 2 is the characteristics root with multiplicity 1
So, the particular solution is of the form:
an(PS) =An12n
or an(PS) =An2n
 Solution of Linear Non-
Homogeneous Recurrence Relation
Substituting the value of an in equation (1) we get,
An2n - 3A(n-1)2n-1 + 2A(n-2)2n-2 = 2n
Dividing both sides by 2n
An – 3A(n−1)/2 + 2A(n−2)/4 = 1
4An - 6A(n-1) + 2An – 4A = 4
4An - 6An + 6A +2An – 4A = 4
A =2
Hence the particular solution is:
an(PS) =2n2n
or an(PS) =n2n+1
 Solution of Linear Non-
Homogeneous Recurrence Relation
Therefore the final solution is:
an = an(GS) + an(PS)
an = 𝜶𝟏 1n + 𝜶𝟐 2n + n2n+1……………..….(3)
To calculate 𝜶1 and 𝜶2 use initial condition a0 = 0 , a1 = 1 in
equation (3)
When n=0 equation (3) becomes
a0 = 𝜶𝟏 10 + 𝜶𝟐 20 + 0*20+1
0 = 𝜶𝟏 + 𝜶𝟐
𝜶𝟏 + 𝜶𝟐 = 0 ………………..(4)
 Solution of Linear Non-
Homogeneous Recurrence Relation
When n=1 equation (3) becomes
a1 = 𝜶𝟏 11 + 𝜶𝟐 21 + 1*21+1
2 = 𝜶𝟏 + 2𝜶𝟐 + 4
𝜶𝟏 + 2𝜶𝟐 = -2………………..(5)
Solving (4) and (5) we get,
𝜶1= 2 and 𝜶2=-2
Putting the value of 𝜶1= 2 and 𝜶2=-2 in equation (3) we get,
an = 2* 1n – 2*2n + n*2n+1
which is the required solution.
 Solution of Linear Non-
Homogeneous Recurrence Relation
Find the solution of recurrence relation of
an =5an-1-6an-2+3n+2n with initial condition a0=0 a1= 1,
and a2 =2
Solution:
Given recurrence relation: an =5an-1-6an-2+3n+2n ……….……(1)
The associated homogeneous part is,
an-5an-1+6an-2= 0
The characteristics equation,
r2 - 5r + 6 = 0
r2 – 2r – 3r + 6 =0
r(r – 2) -3(r-2) = 0
r1 = 2 , r2 = 3
 Solution of Linear Non-
Homogeneous Recurrence Relation
Since the roots are distinct and real so, the general solution is in
the form:
an(GS) = 𝜶𝟏𝒓1𝒏 + 𝜶𝟐𝒓2𝒏
an(GS) = 𝜶𝟏 2n + 𝜶𝟐 3n……….…….(2)

There are two non-homogeneous part as : an= 3n and an= 2n

Let us handle each part separately:
For an= 3n
Here F(n) is polynomial in n, then the particular solution
is of the form:
an(PS1) =An+B
 Solution of Linear Non-
Homogeneous Recurrence Relation
Substituting the value of an in equation (1) we get,
An + B = 5(A(n−1)+B)−6(A(n−2)+B)+3n
An + B = 5(An - A + B) - 6(An - 2A + B) + 3n
Expand and collect terms:
An + B - 5An + 5A - 5B + 6An - 12A + 6B = 3n
2An - 7A - 2B = 3n
Equating the coefficients we get,
2A=3...................(4)
7A -2B = 0.............(5)
 Solution of Linear Non-
Homogeneous Recurrence Relation
Solving equation (4) and (5) we get,
2A = 3
A=3/2
Again,
7A - 2B = 0
0r 7*3/2 =2B
0r B = 21/4
On substituting the value of A and B the particular solution
an(PS1) =An+B will be
an(PS1) =(3/2)n + 21/4
 Solution of Linear Non-
Homogeneous Recurrence Relation
Another non-homogeneous part is: an= 2n
Here 2 is the characteristics root with multiplicity 1
So, the particular solution is of the form:
an(PS2) =An12n
or an(PS2) =An2n
 Solution of Linear Non-
Homogeneous Recurrence Relation
Substituting the value of an in equation (1) we get,
An2n - 5A(n-1)2n-1 + 6A(n-2)2n-2 = 2n
Dividing both sides by 2n
An – 5A(n−1)/2 + 6A(n−2)/4 = 1
4An - 10An + 10A + 6An – 12A = 4
– 2A = 4
A = -2
Hence the particular solution is:
an(PS2) =-2n2n
or an(PS2) =-n2n+1
 Solution of Linear Non-
Homogeneous Recurrence Relation
Therefore the final solution is:
an = an(GS) + an(PS1) + an(PS2 )
an = 𝜶𝟏 2n + 𝜶𝟐 3n + (3/2)n + 21/4 - n2n+1 …..……………(6)
To calculate 𝜶1 and 𝜶2 use initial condition a0 = 0 , a1 = 1 and a2=2
in equation (6)
When n=0 equation (6) becomes
a0 = 𝜶𝟏 20 + 𝜶𝟐 30 + (3/2)0 + 21/4 - 0*2n+1
0 = 𝜶𝟏 + 𝜶𝟐 + 21/4
𝜶𝟏 + 𝜶𝟐 = -21/4 ………………..(7)
 Solution of Linear Non-
Homogeneous Recurrence Relation
When n=1 equation (6) becomes
a1 = 𝜶𝟏 21 + 𝜶𝟐 31 + (3/2)*1 + 21/4 - 1*21+1
1 = 2𝜶𝟏 + 3𝜶𝟐 + 3/2 + 21/4- 4
2𝜶𝟏 + 3𝜶𝟐 = -7/4 ………………..(8)
Solving (7) and (8) we get,
𝜶1= -14 and 𝜶2=35/4
Putting the value of 𝜶1= -14 and 𝜶2=35/4 in equation (6) we get,
an = (-14) 2n + (35/4) 3n + (3/2)n + 21/4 - n2n+1
which is the required solution.
Algorithm
 An algorithm is a sequence of computational steps
that transform the input into the output.
 An algorithm is a sequence of operations performed
on data that have to be organized in the data
structures.
 A finite set of instruction that specify a sequence of
operations to be carried out in order to solve a specific
problem or class of problems is called an algorithm.
 An algorithm is an abstraction of a program to be
executed on a physical machine (model computation).
Algorithm
 An algorithm is defined as set of instructions to
perform a specific task within finite no. of steps.
 Algorithm is defined as a step by step procedure to
perform a specific task within finite number of steps.
 Algorithm can be defined as a sequence of definite
and effective instructions, while terminates with the
production of correct output from the given input.
Characteristics of Algorithm
Characteristics of Algorithm
 Well-defined Inputs
 The expected inputs of an algorithm must be well-
defined to ensure its correctness, predictability, and
repeatability.
 Well-defined inputs ensure that the algorithm's
behavior is deterministic, which means, that the same
input will always produce the same output.
 With well-defined inputs, it is easier to optimize the
algorithm based on the characteristics of the input.
Characteristics of Algorithm
 Well-defined Outputs
 The outputs of an algorithm should be well-defined to
ensure that the algorithm produces the intended and
accurate result for a given set of inputs.
 It avoids ambiguity and guarantees that the algorithm
solves the problem correctly.
 It is also easy to verify the correctness of the algorithm's
implementation.
Characteristics of Algorithm
 Unambiguity
 Ambiguity in the algorithm's description can lead to
incorrect implementations and unreliable results.
 That is why it is important for an algorithm to be
unambiguous.
 It allows the algorithm to be predictable, i.e., the same
input produces the same output, which makes
debugging an implementation easier.
Characteristics of Algorithm
 Finiteness
 The algorithm should end after a finite amount of time,
and it should have a limited number of instructions.
 A finite algorithm ensures that it will eventually stop
executing and produce a result.
 The time and space complexity can be analyzed in the
case of a finite algorithm which is important for
performing further optimizations.
Characteristics of Algorithm
 Language Independent
 A language-independent algorithm can be easily ported
to different programming languages and platforms,
making it more adaptable and usable across various
environments.
 Being language-independent also makes an algorithm
future-proof which means it can be implemented easily
using newer programming languages.
 It also makes it easier to compare the algorithm's
performance using different programming languages.
Characteristics of Algorithm
 Effectiveness and Feasibility
 An algorithm should be feasible because feasibility
indicates that it is practical and capable of being
executed within reasonable constraints and resources.
 It also avoids excessive execution times, which can make
an algorithm unusable in real-world scenarios.
 Feasible algorithms can be easily implemented using
existing hardware infrastructure without using
specialized resources.
 They are adopted easily for usage across different fields
due to its practical hardware requirements.
Algorithm Analysis
 Many times there are more than one ways to solve a
problem with different algorithms and we need a way
to compare multiple ways.
 Also, there are situations where we would like to know
how much time and resources an algorithm might take
when implemented.
 To measure performance of algorithms, we typically
use time and space complexity analysis.
 The idea is to measure order of growths in terms of
input size.
Time Complexity
 The time complexity of an algorithm measures the
amount of time taken by an algorithm to run as a
function of the length of the input.
 Note that the time to run is a function of the length of
the input and not the actual execution time of the
machine on which the algorithm is running on.
 The valid algorithm takes a finite amount of time for
execution.
 The time required by the algorithm to solve given
problem is called time complexity of the algorithm.
Time Complexity
 To estimate the time complexity, we need to consider
the cost of each fundamental instruction and the
number of times the instruction is executed.
Space Complexity
 Problem-solving using computer requires memory to
hold temporary data or final result while the program
is in execution.
 The amount of memory required by the algorithm to
solve given problem is called space complexity of the
algorithm.
 The space complexity of an algorithm measures the
amount of space taken by an algorithm to run as a
function of the length of the input.
Space Complexity
 To estimate the memory requirement we need to focus
on two parts:
 A fixed part:
 It is independent of the input size.
 It includes memory for instructions (code), constants,
variables, etc.
 A variable part:
 It is dependent on the input size.
 It includes memory for recursion stack, referenced
variables, etc.
Best, Worst and Average Case
 In computer science, best, worst, and average case analysis
is a method of analyzing algorithms.
 It defines the amount of time it takes for an algorithm to
run in the best case, worst case, and average case
scenarios.
 The least possible execution time taken by an algorithm for
a particular input is known as best case.
 Best case complexity gives lower bound on the running
time of the algorithm for any instance of input.
 This indicates that the algorithm can never have lower
running time than best case for particular class of
problems.
Best, Worst and Average Case
 The maximum possible execution time taken by an
algorithm for a particular input is known as worst
case.
 Worst case gives upper bound on the running time of
the algorithm for all the instances of the input.
 This ensures that no input can overcome the running
time limit posed by worst case complexity.
 Average case gives average number of steps required
on any instance of the input.
Linear Search/ Sequential search
 Linear search or sequential search is a method for
finding a particular value in a list that consists
checking every one of its elements
 In this method element are searched, one at a time and
in sequence, until the desired one is found.
 A search is said to be unsuccessful if all the elements
are read and the desired element is not found.
 A linear search algorithm can be applied to both
sorted and unsorted list.
Linear Search/ Sequential search
 In case of sorted list, search starts from 0th element
and continues until the element is found or an
element whose value is greater that the value being
searched.
 For unsorted list, search starts from 0th element and
continues until the element is found or up to the last
element in the list.
Linear Search/ Sequential search
 Algorithms:
 Let A[N] be an array of size N.
1. Read the elements of array A
2. Read the Data to be searched.
3. Set Pos=0
4. Repeat step 5 until Pos<N or A[Pos] = Data
5. Increment Pos by 1
 If(Pos<N)

 Display “Search is successful”

6. else
 Display “Search is unsuccessful”

7. Exit
Linear Search/ Sequential search
 Advantages:
 It is simple way for finding an element in a list.
 It can be applied to both sorted and unsorted list.
 Dis-Advantages:
 It is very slow process so can be applied to small size list
only.
Analysis of Linear Search
 Best Case:
 If the desired item is found at the first position in the list
then we will have to make only one comparison.
 Therefore the best case efficiency of linear search is O(1).
 Worst Case:
 If the desired item is stored at the last position in the list
or if it doesn’t exist in the list, we will have to make N
comparisons, where N is the number of items in the list.
 Therefore the worst case efficiency of linear search is
O(N).
Analysis of Linear Search
 Average Case:
 The average case efficiency of linear search can be
determined by finding the average number of
comparisons in best case and worst case i.e. O((1+N)/2)
which is similar to O(N).
Binary Search
 Linear search is inefficient searching solution for large
list.
 An alternate solution that offers better efficiency for
large list is binary search algorithm.
 This algorithm helps us to search data in few
comparisons.
 To apply binary search algorithm, the list to be
searched must be sorted.
Binary Search
 In binary search, we first compare the key with the
item in the middle position of the array.
 If there is a match, the search is successful.
 Otherwise, if the key is lesser than the middle key, the
item to search should lie in the lower half of array
 Else the key is greater than the middle key, the item to
be searched should lie in the upper half of array.
 So we repeat this procedure on the lower and upper
half of the array until the element is found or the
search area is covered.
Binary Search
 Advantages:
 It provides better efficiency for searching in large list.
 Dis-Advantages:
 It requires items in the array to be sorted.
 It is not suitable where there are many insertion and
deletions.
Algorithm of Binary Search
 Let A[N] be an array of sorted elements and key is the item to be searched.
1. Input the sorted array of N elements A[N] and key to be searched.
2. Set LB = 0
3. Set UB= N- 1
4. Set Mid = (LB + UB) / 2
5. If (A[Mid] == key)
 Display “The item is found”
 Exit
6. If (key <A[Mid)
 Set UB =Mid -1
7. If key >A[Mid]
 Set LB=Mid+1
8. If (LB<=UB)
 goto step 4
9. Display “The item is not found”
10. Exit
Analysis of Binary Search
 The best case for this algorithm would be if the item
to be searched is present at the middle position in the
array.
 In this case, the desired item is found in just one
comparison and hence the best case efficiency of
binary search is O(1).
Analysis of Binary Search
 The worst case efficiency would be if the desired record
is not in the array or found in the last bisection.
 In this case, bisection continues until there is only one
element left for comparisons.
 So in 1th bisection, search space is reduced to N/21elements.
 In 2th bisection, search space is reduced to N/22elements.
 In 3rd bisection, search space is reduced to N/23elements.
 Similarly, in ith bisection, search space is reduced to N/2i
elements.
Analysis of Binary Search
 Suppose after ith bisection, the search space is reduced to 1
element.
i.e. N/2i =1
N = 2i
i = log2N (Note: if a = bc then c= logba)

 So the list can be bisected maximum log2N times and each

bisection requires only one comparison.
 Hence the worst case efficiency of binary search is
O(log2N).
Analysis of Binary Search
The average case efficiency of binary search is also
similar to the worst case efficiency i.e. O(log2N).
Example of Binary Search
 Example:
 Suppose an array A has the following elements 5, 8,
12, 25, 30, 40, 55. Trace the binary search if key =30
Sorting Algorithm
 Sorting is the process of arranging data in some logical
order.
 The order can be either ascending, descending and
alphabetical.
 The main objective of sorting is to enhance searching.
 Example:
 Consider we have to retrieve telephone number of a person
name Ram from telephone directory.
 If the names are written randomly then it is very time
consuming and tedious task to retrieve the desired record.
 So one solution is to sort the data so that we can directly start
our search from the name that starts with letter R.
 This reduces the number of record to be searched and hence the
time to search.
Sorting Algorithms
 Different Sorting Algorithms are:
 Insertion sort
 Selection sort
 Bubble sort
 Merge sort
 Shell sort
 Quick sort
 Radix sort
 Heap sort
Insertion Sort
 Insertion sort is implemented by inserting a particular
element at appropriate position.
 The first iteration starts with comparison of 1st element
with 0th element.
 During second iteration, the 2nd element is compared
with 1st and 0th element.
 During third iteration, the 3rd element is compared
with 2nd , 1st and 0th element.
Insertion Sort
 So in general, in every iteration an element is compared
with all the elements before it.
 During the comparison, if it is found suitable position
to be inserted then space is created by shifting the other
elements one position right and inserting the element
at the suitable position.
 This procedure is repeated for all the elements in an
array up to (N-1) iteration.
Insertion Sort (Algorithm)
Let A[N] be the array of N elements.
Insertion Sort (Example)
 Sort the following number using insertion sort.
25, 17, 31, 13, 2
Initially, 25 17 31 13 2
0 1 2 3 4
 In the 1st iteration, we compare the 1st element with the
0th element in the list.
 i.e. 17 is compared with 25, here 17<25 so 17 is inserted
to correct position by shifting other elements one
position right.

0 1 2 3 4
Insertion Sort (Example)
 After 1st iteration list looks like:
17 25 31 13 2
0 1 2 3 4

 In the 2nd iteration, we compare the 2nd element with

the 1st and 0th element in the list.
 i.e. 31 is compared with 25 and 17, here 31>25 so, 31 is
inserted at the same position.
 After 2nd iteration list looks like:
17 25 31 13 2
0 1 2 3 4
Insertion Sort (Example)
 In the 3rd iteration, we compare the 3rd element with the
2nd ,1st and 0th element in the list.
 Here, 13<31, 13<25,13<17, so 13 inserted to correct
position by shifting other elements one position right

17 25 31 13 2
Insertion Sort (Example)
 After 3rd iteration list looks like:
13 17 25 31 2
0 1 2 3 4

 Finally, in the 4th iteration, we compare the 4th

element with the 3rd , 2nd ,1st and 0th element in the list.
 Here, 2<31, 2<25,2<17, an 2<13 so 2 inserted to correct
position by shifting other elements one position right

13 17 25 31 2
Insertion Sort (Example)
 After 4th iteration list looks like:
2 13 17 25 31
0 1 2 3 4

which is the final sorted array.

Question:
Sort the following data using insertion sort
70, 80, 30, 10, 20,99
Analysis of Insertion Sort
 To determine the efficiency, we need to find out the
number of comparisons made.
 Best Case:
 If the list is already sorted, we have to make only one
comparison in each iteration.
 So in N-1 iteration, we will have to make N-1 comparison.
 Therefore the best ease efficiency of insertion sort is O(N).
Analysis of Insertion Sort
 Worst Case:
 The worst case is when the data in the array is in
reversed order.
 Here one comparison is made in first iteration, two
comparison in second iteration, three comparison in
third iteration which leads N-1 comparisons in N-1
iteration.
Analysis of Insertion Sort
 Total number of comparisons =
1 + 2 + 3 +…………+ (N-1)
= N* (N-1)/2
=N2/2 –N/2
 If N is very large then N2 >>>>>>N
 Therefore Big-Oh notation of insertion sort is O(N2).
 Average Case:
The average case efficiency of insertion sort is O(N2).
 In bubble sort, each element is compared with
its adjacent element.
 If the first element is larger than the second
element then the position of the element are
interchanged otherwise it is not changed.
 Then the next element is compared with its
adjacent element and the same process is
repeated for all the elements in the array.
 So at the end of the first iteration the last position
in the list contain the biggest element.

 For the second iteration we compare the adjacent

elements up to N-2 position i.e. the size of list is
reduced by one after every iteration.

 At the end of the second iteration the second last

position in the list contain the second biggest
element.
 Similarly, for the third iteration we compare
the adjacent elements up to N-3position.
 At the end of the third iteration the third last
position in the list contain the third biggest
element.
 This process is continued until the list contains
only one element. After the (N-1) iteration the
list will be sorted.
Let A[N] be the array of N elements.
 Sort the following data using bubble Sort
5, 1, 12, -5, 16 ,2,12,14
Solution,
Initially,
5 1 12 -5 16 2 12 14
0 1 2 3 4 5 6 7

 1st Iteration: Here we compare the adjacent

elements with each other up to (N-1) position.
◦ i.e. we compare 0th element with 1st element, 1st element with 2nd
element, 2nd element with 3rd elements up to (N-2)th and (N-1)th
element.
◦ During the comparison if the first element is greater than second
element then they are interchanged.
1<5, so interchange
5 1 12 -5 16 2 12 14

0 1 2 3 4 5 6 7
-5<12, so interchange

1 5 12 -5 16 2 12 14

0 1 2 3 4 5 6 7
2<16, so interchange

1 5 -5 12 16 2 12 14

0 1 2 3 4 5 6 7
12<16, so interchange

1 5 -5 12 2 16 12 14

0 1 2 3 4 5 6 7
14<16, so interchange

1 5 -5 12 2 12 16 14

0 1 2 3 4 5 6 7

 After 1st iteration list becomes

1 5 -5 12 2 12 14 16

0 1 2 3 4 5 6 7
 1 5 -5 12 2 12 14 16
0 1 2 3 4 5 6 7
 2nd Iteration: Here we compare the adjacent
elements with each other up to (N-2) position.
◦ i.e. we compare 0th element with 1st element, 1st element with
2nd element, 2nd element with 3rd elements up to (N-3)th and
(N-2)th element.
◦ During the comparison if the first element is greater than
second element then they are interchanged.
-5<5, so interchange
1 5 -5 12 2 12 14 16

0 1 2 3 4 5 6 7
2<12, so interchange

1 -5 5 12 2 12 14 16

0 1 2 3 4 5 6 7
After 2nd iteration list becomes:

1 -5 5 2 12 12 14 16

0 1 2 3 4 5 6 7
 1 -5 5 2 12 12 14 16
0 1 2 3 4 5 6 7
 3rd Iteration: Here we compare the adjacent
elements with each other up to (N-3) position.
◦ i.e. we compare 0th element with 1st element, 1st element with
2nd element, 2nd element with 3rd elements up to (N-4)th and
(N-3)th element.
◦ During the comparison if the first element is greater than
second element then they are interchanged.
-5<1, so interchange
1 -5 5 2 12 12 14 16

0 1 2 3 4 5 6 7
2<5, so interchange

-5 1 5 2 12 12 14 16

0 1 2 3 4 5 6 7
After 3rd iteration list becomes:

-5 1 2 5 12 12 14 16

0 1 2 3 4 5 6 7
 -5 1 2 5 12 12 14 16
0 1 2 3 4 5 6 7
 4th Iteration: Here we compare the adjacent
elements with each other up to (N-4) position.
◦ i.e. we compare 0th element with 1st element, 1st element with
2nd element, 2nd element with 3rd elements up to (N-5)th and
(N-4)th element.
◦ During the comparison if the first element is greater than
second element then they are interchanged.
 -5 1 2 5 12 12 14 16

0 1 2 3 4 5 6 7
 5th Iteration: Here we compare the adjacent
elements with each other up to (N-5) position.
◦ i.e. we compare 0th element with 1st element, 1st element with
2nd element, 2nd element with 3rd elements up to (N-6)th and
(N-5)th element.
◦ During the comparison if the first element is greater than
second element then they are interchanged.

-5 1 2 5 12 12 14 16
0 1 2 3 4 5 6 7
 -5 1 2 5 12 12 14 16

0 1 2 3 4 5 6 7
 6th Iteration: Here we compare the adjacent
elements with each other up to (N-6) position.
◦ i.e. we compare 0th element with 1st element, 1st element with
2nd element, 2nd element with 3rd elements up to (N-7)th and
(N-6)th element.
◦ During the comparison if the first element is greater than
second element then they are interchanged.

-5 1 2 5 12 12 14 16
0 1 2 3 4 5 6 7
 -5 1 2 5 12 12 14 16

0 1 2 3 4 5 6 7
 7th Iteration: Here we compare the adjacent
elements with each other up to (N-7) position.
◦ i.e. we compare 0th element with 1st element, 1st element with
2nd element, 2nd element with 3rd elements up to (N-8)th and
(N-7)th element.
◦ During the comparison if the first element is greater than
second element then they are interchanged.
-5 1 2 5 12 12 14 16

0 1 2 3 4 5 6 7
This is our final sorted array using bubble sort
 There are N-1 comparisons in 1st iteration, N-
2 in 2nd iteration, N-3 in 3rd iteration.
 so total number of comparison
=(N-1) +(N-2)+ (N-3) +………+3 + 2 + 1
= N*(N-1)/2
= N2/2-N/2
 Therefore the efficiency of selection sort is
O(N2) ) i.e. time taken to execute algorithm
increases quadratically with increase in input
data.
Application to Algorithm Analysis

Explore Yourself!!!!
End of Chapter 4
Thank You !!!!