WELCOME TO

SECOND YEAR
SEM- IV
AOA (ANALYSIS OF
ALGORITHM)
 C O U R S E O U T C O M E S

CO1- Apply algorithmic fundamentals to perceive various

algorithmic approaches.

CO2- Apply various algorithm approaches to solve the classical

problems.

CO3- Analyze the complexity of Divide and Conquer & Iterative

Strategies.

CO4- Analyze the complexity of Greedy and Dynamic

Programming Strategies.

CO5- Analyze the complexity of Backtracking & Branch and

Bound Strategies.

CO6- Compare the approaches for various algorithms.

INTRODUCTION To
AOA

CHAPTER-1
CO1- Apply algorithmic fundamentals to perceive various
algorithmic approaches.
 What is an algorithm?
Algorithm is a set of steps to complete a task.
For example,
Task: to make a cup of tea.
Algorithm:
• Add water and milk to the kettle,
• Boil it, add tea leaves,
• Add sugar, and then serve it in cup.
 Definition: “An algorithm is a procedure to
solve a particular problem in a finite no. of steps for a
finite size input.”
 A n algorithm is thus a sequence of computational
steps that transform the input into the output.
 We can also view an algorithm as a tool for solving
a well-specified computational problem
Properties of a good
algorithm
• May take Zero or more input
Input • Input may be scalar, vector, array, tree, graph etc

• Produce at least one output

Outpu • Output may be scalar, vector, array, tree, graph etc
t
• Instructions should be simple, precise and concise
Definitenes • There should not be multiple ways to interpret the same
s instn.

Finitenes • Every algorithm must terminate

s
Effectivenes • Algorithm should be written with basic set of instructions
s
 Introduction to algorithm
Performance Analysis
 Space and time complexity
 Growth of function
 Big- Oh, Omega, Theta notation
 PERFORMANCE ANALYSIS

 Space Complexity
 Time Complexity
 Growth of a
function
 PERFORMANCE ANALYSIS

Space Complexity S(n)

 The amount of memory required by an algorithm to solve
given
problem is called space complexity.
 Example-1: Addition of two scalar variables
 The addition of two scalar numbers requires one
extra memory location to hold the result. Thus
space complexity of this algorithm is constant
S(n)=O(1)
 Example-2: Addition of two arrays
 The addition of two arrays of size ‘n’
requires ‘n’ extra memory locations to hold
 PERFORMANCE ANALYSIS

Time Complexity T(n)

 The time required by the algorithm to solve the
given
problem is called time complexity.
 Time complexity is measured in number of
primitive operations.
 Primitive operation is the most frequent
operation in
algorithm.
 PERFORMANCE ANALYSIS

Time Complexity
 Example-1: Addition of two scalar variables
 The addition of two scalar numbers requires
one addition operation. Thus time complexity
of this algorithm is T(n)=O(1).
 PERFORMANCE ANALYSIS

Time Complexity
 Example-2: Addition of two arrays
for i 1 to n do
C[i] A[i] + B[i]
Total time of algorithm is measured as
T(n)= 1 Initialization + n (Comparison + Increment +
Addition + Assignment)

= 1+ 4n
Thus time required for given algorithm is
T(n) = O(n)
 PERFORMANCE ANALYSIS
Growth of Function
 The efficiency of the algorithm is expressed in terms
of
input size n.
 The relationship between input size and performance
of the algorithm is called order of growth.
 Order of growth indicates how quickly the time
required
by algorithm grows with respect to input size.

1< log n <√ n < n < n log n < n^2 < n^3 < ..
 PERFORMANCE ANALYSIS

Growth of
Function
Input Constant Linear Quadratic Cubic Exponent
Size (1) (n) (n2) (n3) (2n )
1 1 1 1 1 1
2 1 2 4 8 4
3 1 3 9 27 8
4 1 4 16 64 16
8 1 8 64 512 256
16 1 16 256 4096 66536
32 1 32 1024 32678 4294967296
 PERFORMANCE ANALYSIS
Big- Oh, Omega, Theta notation (Asymptotic Notations)
 Asymptotic notations are mathematical tool to find
time or space complexity of an algorithm without
implementing it in a programming language.
Asymptotic notations

Big Oh(O)

Big Omega(Ω)

Big Theta(θ)
 PERFORMANCE ANALYSIS

Big Oh(O)

 Big oh notation defines upper bound for the

algorithm
 It means running time of algorithm can not more
than its asymptotic upper bound for any random
sequence of data
 PERFORMANCE ANALYSIS

Big
Oh(O)
 Let f(n) and are two
nonnegative
g(n) functions
indicating running time of two
algorithms.
 We say, g(n) is upper bound of
f(n) if there exist some positive
constant c and no such that ,
f(n) ≤ c. g(n) for all n ≥ no
where, no ≥ 1, c > 0
 PERFORMANCE ANALYSIS
B ig Oh(O) for c=1 and n=2
3*2+2 ≤ 1*2 => 8 Fals
Let, ≤2 e
f(n)= 3n+2 for c=2 and n=2 Fals
g(n)=n 3*2+2 ≤ 2*2 => 8 e
Can we say f(n) =O(g(n)) ≤4
Fals
iff
f(n) ≤ c. g(n) for c>0 and n0 for c=3 and n=2 e
≥ 1
Putting f(n) and g(n) in above 3*2+2 ≤ 3*2 => 8
eqn ≤6 True
3n+2
Now ≤ wec. n ……
will (1)check when for c=4 and n=2
this condition is true by 3*2+2 ≤ 4*2 => 8
changing values of c ≤8
 PERFORMANCE ANALYSIS

Big
Oh(O)

Putting c=4 in equation 3n+2 ≤ c. n ……

(1) (1)
3n+2 ≤ 4n
After solving this
equation 2 ≤ 4n -3n
2 ≤n
for n ≥ 2 and f(n) ≤ c. is always
c=4 g(n)
So we can say that true
f(n)=O(g(n))
 PERFORMANCE ANALYSIS

• 1< log n <√ n < n < n log n < n^2 < n^3 < .. < 2^n..<n^n
 PERFORMANCE ANALYSIS

Big Omega(Ω)

 Big Omega notation lower bound for

defines algorithm. the
 It means the running time of algorithm cannot
be less than its asymptotic lower bound for
any random sequence of data
 PERFORMANCE ANALYSIS
Big
Omega(Ω)
 Let f(n) g(n) are two
nonnegative
and
functions indicating
running time of two
algorithms
 We say the function g(n)
is lower bound of function
f(n) if there exists some
positive
c.g(n) ≤ f(n)constant
for all n c
≥ & n0
such that
where, no ≥ 1, c n0
 PERFORMANCE ANALYSIS

B ig Omega(Ω) for c=1 and n=1

1* 1 ≤ 3* 1+2 1
Let, ≤ 5 True
f(n)= 3n+2 Putting c=1 in
g(n)=n equation 1 1* n ≤
Can we say f(n) =Ω (g(n)) 3n+2
c.iff
g(n) ≤ f(n) for c>0 and n0 After solving this
≥ 1
Putting f(n) and g(n) in above equation
eqn n ≤ 3n + 2
f(n) ≤ c. is always
c. n ≤ 3n+2 …… (1) g(n)we true say
So can
Lets take n=1 and now we for n = 1 and
f(n)=Ω(g(n thatc=1
will check when this condition ))
 PERFORMANCE ANALYSIS

B ig Omega(Ω) In this we can not find

any c value which
Let, satisfy the condition
f(n)= 3n+2
g(n)=n2 So we can say
f(n) ≠ Ω(g(n)) that
Can we say f(n) =Ω
(g(n))
c. g(n) ≤ f(n) for c>0 and n0
≥ 1 Means f(n) not
Putting f(n) and g(n) in above
is lower
eqn
bounded n2
c. n ≤ 3n+2 …… (1)
But it can be upper
Lets take n=1 and now we
bounded by n2
will check when this condition
 PERFORMANCE ANALYSIS

Big Theta(θ)

 Big Theta notation both bound for

defines algorithm. the
 This is Average Case Scenario
 It means the running time of algorithm cannot
be less than or greater than its asymptotic tight
bound for any random sequence of data
 PERFORMANCE ANALYSIS

Big Theta(θ)

 Let f(n) and g(n) are

two nonnegative functions
indicating running time of two
algorithms
 We say the function g(n) is
tight bound of function f(n)
if there exists some positive
constant c1 , c2 & n0 such that
c1.g(n) ≤ f(n) ≤ c2.g(n) for all n
≥ n0 where, no ≥ 1, c1 , c2 > 0
 PERFORMANCE ANALYSIS
Big Theta(θ)
•We have seen that for
Let, c=4 f(n) is upper bound
f(n)= 3n+2 of g(n) 3n+2 ≤ 4n
g(n)=n •&
Can we say f(n) = θ (g(n)) • for c=1f(n) is lower
iff
c1.g(n) ≤ f(n) ≤ c2.g(n) for all n bound of
≥
Putting f(n) and g(n) in above • g(n) n ≤ 3n
n0 +2
eqn c1. n ≤ 3n+2 ≤ c1. n …… (1)

Now we have check when •So we can say

this condition is true by that
changing values of c1 , c2 f(n)=θ(g(n))
 PERFORMANCE ANALYSIS

O
Worst
Ω Bes θ Average
Case t Case
Cas
e
We will take Linear Search
example
8 4 7 2 9 3 1 6 5
0 1 2 3 4 5 6 7… n

Worst Case (O) O(n)

Best Case (Ω) Ω(1) W h e n O a n d Ω are
same
Average Case (θ) θ(n/2) the we will use θ
 Mathematical background for algorithm
analysis
MATHEMATICAL BACKGROUND FOR ALGORITHM
ANALYSIS
Before we start analysing algorithm, we will
first look at some important mathematical
𝑛
formulas
𝛴 1 = 1 + 1 + 1 + ⋯ + 1 = 𝑛 = 0 (2𝑛)
𝑛 𝑛+ 𝑛
𝛴ⅈ=1ⅈ = 1 + 2 + 3 + ⋯ + 𝑛
𝑛 𝑖=1
1 2 = =0
+𝑛 2
= 𝛴𝑛 = 𝑛2

𝛴ⅈ=1 = 1 +
𝑛
ⅈ𝑘 2𝑘 + 3𝑘 … 𝑛𝑘
𝑘+ =𝑜
+ 𝑛𝑘 = 1
𝑛
𝑘+1
𝛴ⅈ=1𝑘ⅈ = 𝑘 + 𝑘 2 + 𝑘 3 + ⋯
𝑛 𝑘𝑛+1 = 𝑂
𝑘−
+ 𝑘𝑛 = 𝑘𝑛
1
 Complexity class :Definition of P, NP, NP-
Hard,
NP-Complete
 COMPLEXITY CLASS

 Types of Complexity Classes

Complexity classes are useful in organizing similar types of
problems.:

 P Class
 NP Class
 NP-hard
 NP-complete
 P CLASS

• The P in the P class stands for Polynomial Time.

• It is the collection of decision problems(problems with a “yes” or
“no” answer) that can be solved by a deterministic machine in
polynomial time.

Features:
• The solution to P problems is easy to find.
• P is often a class of computational problems that are
solvable and tractable.
• Tractable means that the problems can be solved in theory
as well as in practice.
• But the problems that can be solved in theory but not in
practice are known as intractable.
 N P C L A S S

• The NP in NP class stands for Non-deterministic Polynomial

Time.
• It is the collection of decision problems that can be solved by a non-
deterministic machine in polynomial time.
Features:
• The solutions of the NP class are hard to find since they are
being solved by a non-deterministic machine but the
solutions are easy to verify.
• Problems of NP can be verified by a Turing machine in
polynomial time.
 N P - H A R D C L A S S

• An NP-hard problem is at least as hard as the hardest problem in

NP and it is a class of problems such that every problem in NP
reduces to NP-hard.

Features:
All NP-hard problems are not in NP.
It takes a long time to check them. This means if a solution for
an NP-hard problem is given then it takes a long time to check
whether it is right or not.
A problem A is in NP-hard if, for every problem L in NP, there
exists a polynomial-time reduction from L to A.
1.2
 Analyzing time and space complexity of
Iterative algorithm-
 Insertion Sort
 Selection Sort
 ANALYSIS OF ALGORITHM

Algorithm

Iterative Recursiv
e
A() A(n)
{ {
for i=1 to n if( )
Max(a,b) A (n/2)
}
}
 ANALYSIS OF ALGORITHM

Algorithm

Iterative Recursiv
e
Selection Sort
Recurrences
Insertion Sort
 ANALYSIS OF ITERATIVE ALGORITHM
Iterative Algorithm
Analysis

A() {
O(n
for(i=1
int i; to n)
)
print(“comp”);
}
A() {
int i, j
for(i=1 to n) O(n2
for (j=1 to )
n)
 ANALYSIS OF SELECTION SORT

• Selection Sort is a comparison-based sorting algorithm. It sorts an array

by repeatedly selecting the smallest (or largest) element from the
unsorted portion and swapping it with the first unsorted element.
• This process continues until the entire array is sorted.
• First we find the smallest element and swap it with the first element. This
way we get the smallest element at its correct position.
• Then we find the smallest among remaining elements (or second
smallest) and swap it with the second element.
• We keep doing this until we get all elements moved to correct position.
 ANALYSIS OF SELECTION SORT

•Algorithm SELECTION SORT (A)

Pass-1
// A is an array of size n

for i = 0 to n - 1 do min = i
for j = i+1 to n do
if A[j] < A[min] do
min = j ;
end if
end for
swap (A[min], A[i]);
end for
 ANALYSIS OF SELECTION SORT

•Algorithm SELECTION SORT (A)

•// A is an array of size n
0 1 2 3 4 5

• for i = 0 to n - 1 do min =
14 33 27 10 35 19
i
• for j = i+1 to n do Pass-1
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 ANALYSIS OF SELECTION SORT
0 1 2 3 4 5
•Algorithm SELECTION SORT (A)
14 33 27 10 35 19
•// A is an array of size n

i
• for i = 0 to n - 1 do min =
i
• for j = i+1 to n do Pass-1
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 ANALYSIS OF SELECTION SORT
0 1 2 3 4 5

•Algorithm SELECTION SORT (A)

14 33 27 10 35 19
•// A is an array of size n
i
• for i = 0 to n - 1 do min = i min =0
• for j = i+1 to n do
• if A[j] < A[min] do Pass-1
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 ANALYSIS OF SELECTION SORT

•Algorithm SELECTION SORT (A) 0 1 2 3 4 5

•// A is an array of size n 14 33 27 10 35 19

• for i = 0 to n - 1 do min = i
i j
• for j = i+1 to n do
min =0
• if A[j] < A[min] do
•min = j; end if
Pass-1
• end for
• swap (A[min], A[i]);
•end for
 ANALYSIS OF SELECTION SORT
0 1 2 3 4 5
•Algorithm SELECTION SORT (A) 14 33 27 10 35 19
•// A is an array of size n

i j
• for i = 0 to n - 1 do min = i
• for j = i+1 to n do
min =0
• if A[j] < A[min] do Pass-1
•min = j; end if 33 <
• end for 14
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5

14 33 27 10 35 19
•Algorithm SELECTION SORT (A)
•// A is an array of size n i j
min =0
• for i = 0 to n - 1 do min = i
• for j = i+1 to n do Pass-1
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5

14 33 27 10 35 19
•Algorithm SELECTION SORT (A)
•// A is an array of size n i j
min =0
• for i = 0 to n - 1 do min =
i Pass-1
27 <
• for j = i+1 to n do
14
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
 0 1 2 3 4 5
•Algorithm SELECTION SORT (A)
14 33 27 10 35 19
•// A is an array of size n

• for i = 0 to n - 1 do min = i i j
• for j = i+1 to n do min =0
• if A[j] < A[min] do
•min = j; end if Pass-1
• end for
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A) 0 1 2 3 4 5
•// A is an array of size n 14 33 27 10 35 19

• for i = 0 to n - 1 do min = i
i j
• for j = i+1 to n do
• if A[j] < A[min] do min =0
•min = j; end if
Pass-1
• end for 10 <
• swap (A[min], A[i]); 14
•end for
•Algorithm SELECTION SORT (A)
•// A is an array of size n 0 1 2 3 4 5

14 33 27 10 35 19
• for i = 0 to n - 1 do min =
i
i j
• for j = i+1 to n do
min =3
• if A[j] < A[min] do
•min = j; end if Pass-1
10 <
• end for
14
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
14 33 27 10 35 19
• for i = 0 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do
min =3
•min = j; end if
• end for Pass-1
• swap (A[min], A[i]);
10 <
14
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
14 33 27 10 35 19
• for i = 0 to n - 1 do min =
i i j
• for j = i+1 to n do min =3
• if A[j] < A[min] do
Pass-1
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
•// A is an array of size n 0 1 2 3 4 5

14 33 27 10 35 19
• for i = 0 to n - 1 do min = i
• for j = i+1 to n do
• if A[j] < A[min] do
i j
•min = j; end if min =3
• end for
Pass-1
• swap (A[min], A[i]); 35 <
•end for 10
•Algorithm SELECTION SORT (A)
•// A is an array of size n 0 1 2 3 4 5

14 33 27 10 35 19
• for i = 0 to n - 1 do min = i
• for j = i+1 to n do
• if A[j] < A[min] do
i j
•min = j; end if min =3
• end for
Pass-1
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
14 33 27 10 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do
min =3
•min = j; end if
• end for Pass-1
• swap (A[min], A[i]);
19 <
10
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
14 33 27 10 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do min =3
•min = j; end if
• end for Pass-1
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
14 33 27 10 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do min =3
•min = j; end if
• end for Pass-1
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A) 0 1 2 3 4 5
•// A is an array of size n 10 33 27 14 35 19

• for i = 1 to n - 1 do min = i
i j
• for j = i+1 to n do
• if A[j] < A[min] do min =3
•min = j; end if
Pass-1
• end for
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n 10 33 27 14 35 19

• for i = 1 to n - 1 do min =
i i
• for j = i+1 to n do
• if A[j] < A[min] do Pass-2
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do
i
• if A[j] < A[min] do
•min = j; end if min =1
• end for Pass-2
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19

• for i = 1 to n - 1 do min =
i i j
• for j = i+1 to n do min =1
• if A[j] < A[min] do
Pass-2
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A) 0 1 2 3 4 5
•// A is an array of size n 10 33 27 14 35 19

• for i = 1 to n - 1 do min = i
• for j = i+1 to n do
i j
• if A[j] < A[min] do min =1
•min = j; end if
Pass-2
• end for 27 <
• swap (A[min], A[i]); 33
•end for
 0 1 2 3 4 5
•Algorithm SELECTION SORT (A)
10 33 27 14 35 19
•// A is an array of size n

• for i = 1 to n - 1 do min = i i j
• for j = i+1 to n do min =2
• if A[j] < A[min] do
•min = j; end if Pass-2
27 <
• end for 33
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min =
i i j
• for j = i+1 to n do
min =2
• if A[j] < A[min] do
•min = j; end if Pass-2
27 <
• end for 33
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do
min =2
•min = j; end if
• end for Pass-2
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do min =2
•min = j; end if
• end for Pass-2
14< 27
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
•// A is an array of size n 0 1 2 3 4 5

10 33 27 14 35 19
• for i = 1 to n - 1 do min =
i
i j
• for j = i+1 to n do
min =3
• if A[j] < A[min] do
•min = j; end if Pass-2
14< 27
• end for
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do
•min = j; end if
min =3
• end for Pass-2
• swap (A[min], A[i]);
14< 27
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do
•min = j; end if
min =3
• end for Pass-2
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do
min =3
•min = j; end if
• end for Pass-2
• swap (A[min], A[i]);
35< 14
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do min =3
•min = j; end if
• end for Pass-2
35< 14
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do min =3
•min = j; end if
• end for Pass-2
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
•// A is an array of size n 0 1 2 3 4 5

10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do
• if A[j] < A[min] do
i j
•min = j; end if min =3
• end for
Pass-2
• swap (A[min], A[i]); 19< 14
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do
•min = j; end if
min =3
• end for Pass-2
• swap (A[min], A[i]);
19< 14
•end for
•Algorithm SELECTION SORT (A) 0 1 2 3 4 5
•// A is an array of size n 10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do min =3
•min = j; end if
Pass-2
• end for
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 33 27 14 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do min =3
•min = j; end if
• end for Pass-2
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 14 27 33 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do
• if A[j] < A[min] do
i j
•min = j; end if min =3
• end for
• swap (A[min], A[i]); Pass-2
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 14 27 33 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do
i
• if A[j] < A[min] do
•min = j; end if min =3
• end for Pass-3
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 14 27 33 35 19
• for i = 1 to n - 1 do min =
i i
• for j = i+1 to n do
min =2
• if A[j] < A[min] do
•min = j; end if Pass-3
• end for
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 14 27 33 35 19
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i j
• if A[j] < A[min] do
•min = j; end if
min =2
• end for Pass-3
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5

10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =2
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do 33< 27
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5

10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =2
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do 33< 27
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5

10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =2
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5

10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =2
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do 35< 27
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =2
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do 35< 27
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =2
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =2
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do 19< 27
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do 19< 27
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do 19< 27
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 27 33 35 19

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-3
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i
•// A is an array of size n
min =3
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A) j

i
•// A is an array of size n
min =3
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A) j

i
•// A is an array of size n
min =3
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do 35< 33
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A) j

i
•// A is an array of size n
min =3
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do 35< 33
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =3
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =3
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do 27< 33
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do 27< 33
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do 27< 33
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i j
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 33 35 27

•Algorithm SELECTION SORT (A)

i
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-4
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 27 35 33

•Algorithm SELECTION SORT (A)

i
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-5
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 27 35 33

•Algorithm SELECTION SORT (A)

i
•// A is an array of size n
min =4
• for i = 1 to n - 1 do min = i
Pass-5
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 27 35 33

•Algorithm SELECTION SORT (A)

•// A is an array of size n i j
min =4
• for i = 1 to n - 1 do min = i
Pass-5
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 27 35 33

•Algorithm SELECTION SORT (A)

•// A is an array of size n i j
min =4
• for i = 1 to n - 1 do min = i
Pass-5
• for j = i+1 to n do 33< 35
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 27 35 33

•Algorithm SELECTION SORT (A)

•// A is an array of size n i j
min =5
• for i = 1 to n - 1 do min = i
Pass-5
• for j = i+1 to n do 33< 35
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 27 35 33

•Algorithm SELECTION SORT (A)

•// A is an array of size n i j
min =5
• for i = 1 to n - 1 do min = i
Pass-5
• for j = i+1 to n do 33< 35
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 27 35 33

•Algorithm SELECTION SORT (A)

•// A is an array of size n i j
min =5
• for i = 1 to n - 1 do min = i
Pass-5
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 27 35 33

•Algorithm SELECTION SORT (A)

i
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-5
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
 0 1 2 3 4 5
ANALYSIS OF SELECTION SORT
10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

i
•// A is an array of size n
min =5
• for i = 1 to n - 1 do min = i
Pass-5
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
•Algorithm SELECTION SORT (A)
0 1 2 3 4 5
•// A is an array of size n
10 14 19 27 33 35
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do i
• if A[j] < A[min] do min =5
•min = j; end if
• end for Pass-5
• swap (A[min], A[i]);
•end for
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n i Value Number of No of
Comparison Swap
s s
• for i = 1 to n - 1 do min = i
• for j = i+1 to n do
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n
i Value Number of No of
• for i = 1 to n - 1 do min = i Comparisons Swaps
• for j = i+1 to n do i= 1
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n
i Value Number of No of
• for i = 1 to n - 1 do min = i Comparisons Swaps
• for j = i+1 to n do i= 1 n-1 1
• if A[j] < A[min] do
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n
i Value Number of No of
• for i = 1 to n - 1 do min = i Comparisons Swaps
• for j = i+1 to n do i= 1 n-1 1
• if A[j] < A[min] do i= 2
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n
i Value Number of No of
• for i = 1 to n - 1 do min = i Comparisons Swaps
• for j = i+1 to n do i= 1 n-1 1
• if A[j] < A[min] do i= 2 n-2 1
•min = j; end if
• end for
• swap (A[min], A[i]);
•end for
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n
i Value Number of No of
• for i = 1 to n - 1 do min = i Comparisons Swaps
• for j = i+1 to n do i= 1 n-1 1
• if A[j] < A[min] do i= 2 n-2 1
•min = j; end if
• end for i= 3

• swap (A[min], A[i]);

•end for
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n
i Value Number of No of
• for i = 1 to n - 1 do min = i Comparisons Swaps
• for j = i+1 to n do i= 1 n-1 1
• if A[j] < A[min] do i= 2 n-2 1
•min = j; end if
• end for i= 3 n-3 1

• swap (A[min], A[i]);

•end for
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n
i Value Number of No of
• for i = 1 to n - 1 do min = i Comparisons Swaps
• for j = i+1 to n do i= 1 n-1 1
• if A[j] < A[min] do i= 2 n-2 1
•min = j; end if
• end for i= 3 n-3 1

• swap (A[min], A[i]); …. …. ….

•end for
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n
i Value Number of No of
Comparison Swap
• for i = 1 to n - 1 do min = i s s
• for j = i+1 to n do i= 1 n-1 1
• if A[j] < A[min] do
i= 2 n-2 1
•min = j; end if
• end for i= 3 n-3 1
• swap (A[min], A[i]); …. …. ….
•end for
i = n-1
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35

•Algorithm SELECTION SORT (A)

•// A is an array of size n
i Value Number of No of
Comparison Swap
• for i = 1 to n - 1 do min = i s s
• for j = i+1 to n do i= 1 n-1 1
• if A[j] < A[min] do
i= 2 n-2 1
•min = j; end if
• end for i= 3 n-3 1
• swap (A[min], A[i]); …. …. ….
•end for
i = n-1 1 1
ANALYSIS OF SELECTION SORT
Worst Case

0 1 2 3 4 5

10 14 19 27 33 35
i Value Number of No of
•Algorithm SELECTION SORT (A) Comparison Swap
•// A is an array of size n
s s
i= 1 n-1 1

• for i = 1 to n - 1 do min = i i= 2 n-2 1

• for j = i+1 to n do i= 3 n-3 1
• if A[j] < A[min] do …. …. ….
•min = j; end if
i = n-1 1 1
• end for
= [(n-1) + (n-2) + (n-3) + …..+ 1] +
• swap (A[min], A[i]); [1+1..+1]
+ 𝑛= + n=
2
𝑛 𝑛 +𝑛
𝑛+1
2 2
•end for
O(n2)
ANALYSIS OF SELECTION SORT

0 1 2 3 4 5

10 14 19 27 33 35
i Value Number of No of
•Algorithm SELECTION SORT (A) Comparison Swap
•// A is an array of size n
s s
i= 1 n-1 1

• for i = 1 to n - 1 do min = i i= 2 n-2 1

• for j = i+1 to n do i= 3 n-3 1
• if A[j] < A[min] do …. …. ….
•min = j; end if
i = n-1 1 1
• end for
= [(n-1) + (n-2) + (n-3) + …..+ 1] +
• swap (A[min], A[i]); [1+1..+1]
+ 𝑛 = 𝑛 +𝑛
2
𝑛
𝑛+1
+ 𝑛= O(n2)
2 2
•end for =
ANALYSIS OF SELECTION SORT
Best Case

0 1 2 3 4 5

10 14 19 27 33 35
i Value Number of
•Algorithm SELECTION SORT (A) Comparison
•// A is an array of size n
s
i= 1 n-1

• for i = 1 to n - 1 do min = i i= 2 n-2

• for j = i+1 to n do i= 3 n-3
• if A[j] < A[min] do …. ….
•min = j; end if
i = n-1 1
• end for
= [(n-1) + (n-2) + (n-3) +
• swap (A[min], A[i]); …..+ 1]
2
𝑛 𝑛 +𝑛
𝑛+1
2 2
•end for = = =
Ω(n )
2
 ANALYSIS OF SELECTION SORT

Space Complexity

• Selection sort is an in-

•Algorithm SELECTION SORT (A) place
algorithm
•// A is an array of size n
• . It performs all computation
in the original array and no
other array is used.
• for i = 1
to n - 1 do
• Variables min, i , j are
min = i required for any input n
• Hence, the space complexity
• for j = i+1
to n do works out to be O(1).
• if A[j] <
A[min]
do
•m
in
 ANALYSIS OF INSERTION SORT

 Insertion sort works the way

man y people sort a h an d of playing
cards.
 We start wi th an e m p t y left h an d
and the cards face down on the
table. We th en remov e one card at
a time from the table an d insert
it into the correct position in
the left hand.
 To fi nd the correct position for a
card, we compare it wi th each of
the cards already in the hand,
from right to left,
 At all times, the cards held in the
 ANALYSIS OF INSERTION SORT
INSERTION-SORT (ARR, N)
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i]
Step 3: SET j = i - 1
Step 4: Repeat while j>=0 &&
a[j]>Temp
SET ARR[j + 1] = ARR[j]
SET j = j - 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
 INSERTION-SORT (ARR, N)
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 0 1 2 3 4 5
1 8 2 4 9 3 6
Step 2: SET TEMP = ARR[i]
Step 3: SET j = i - 1
Step 4: Repeat while
j>=0 && a[j]>Temp
SET ARR[j + 1] = ARR[j]
SET j = j - 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF
LOOP] Step 6:
EXIT
 INSERTION-SORT (ARR, N)
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1 0 1 2 3 4 5
Step 2: SET TEMP = ARR[i]
8 2 4 9 3 6
Step 3: SET j = i - 1
Step 4: Repeat while j>=0 &&
a[j]>Temp
SET ARR[j + 1] = ARR[j]
SET j = j - 1 Pass-1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
 INSERTION-SORT (ARR, N)
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1 0 1 2 3 4 5
Step 2: SET TEMP = ARR[i]
8 2 4 9 3 6
Step 3: SET j = i - 1
Step 4: Repeat while j>=0 &&
a[j]>Temp i
SET ARR[j + 1] = ARR[j]
SET j = j - 1 Pass-1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
 INSERTION-SORT (ARR, N)
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1 0 1 2 3 4 5
Step 2: SET TEMP = ARR[i]
8 2 4 9 3 6
Step 3: SET j = i - 1
Step 4: Repeat while j>=0 &&
a[j]>Temp i
SET ARR[j + 1] = ARR[j]
SET j = j - 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 8 2 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 8 2 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 2≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 8 2 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 2≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 8 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 2≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 8 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j=- i
a[j]>Temp 1
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 2≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 8 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j=- i
a[j]>Temp 1
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 2≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 8 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j=- i
a[j]>Temp 1
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 2≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 8 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j=- i
a[j]>Temp 1
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 2≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j=- i
a[j]>Temp 1
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-1 Temp = 2
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 2≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp = 4
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp = 4
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp = 4
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 4≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 4 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp = 4
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 4≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp = 4
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 4≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp = 4
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 4≤2
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp = 4
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 4≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 8 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp = 4
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 4≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-2 Temp = 4
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 4≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-3 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-3 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-3 Temp = 9
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-3 Temp = 9
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-3 Temp = 9
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 9≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-3 Temp = 9
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 9≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤9
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 3 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤9
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤9
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤9
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 9 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤9
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤4
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 8 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤4
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤4
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤4
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤2
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤2
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 4 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤2
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-4 Temp = 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 3≤2
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤9
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 6
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤9
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤9
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤9
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 9 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 && j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤8
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤4
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤4
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 8 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤4
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp = 6
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP 6≤4
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
j i
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1 Pass-5 Temp
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i Va lue Comparison Swap
a[j]>Temp
1
SET ARR[j+ 1] = ARR[j]
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i Va lue Comparison Swap
a[j]>Temp
1
SET ARR[j+ 1] = ARR[j]
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i Va lue Comparison Swap
a[j]>Temp
1 1 1
SET ARR[j+ 1] = ARR[j]
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i Va lue Comparison Swap
a[j]>Temp
1 1 1
SET ARR[j+ 1] = ARR[j] 2
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i Va lue Comparison Swap
a[j]>Temp
1 1 1
SET ARR[j+ 1] = ARR[j] 2
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i Va lue Comparison Swap
a[j]>Temp
1 1 1
SET ARR[j+ 1] = ARR[j] 2 2 2
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i Va lue Comparison Swap
a[j]>Temp
1 1 1
SET ARR[j+ 1] = ARR[j] 2 2 2
SET j = j- 1 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i Va lue Comparison Swap
a[j]>Temp
1 1 1
SET ARR[j+ 1] = ARR[j] 2 2 2
SET j = j- 1 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
i Va lue Comparison Swap
a[j]>Temp
1 1 1
SET ARR[j+ 1] = ARR[j] 2 2 2
SET j = j- 1 3 3 3
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
i Va lue Comparison Swap
Step 4: Repeat while j>=0 &&
1 1 1
a[j]>Temp
2 2 2
SET ARR[j+ 1] = ARR[j]
3 3 3
SET j = j- 1
… … …
[END OF INNER LOOP]
n-1 n-1 n-1
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
i Compar Swap Total
Step 4: Repeat while j>=0 &&
Va lue i son
a[j]>Temp 1 1 1 1+1=2
SET ARR[j+ 1] = ARR[j] 2 2 2 2+2=4
SET j = j- 1 3 3 3 3+3=6
[END OF INNER LOOP] … … … ----
Step 5: SET ARR[j + 1] = TEMP n-1 n-1 n-1 2n-2
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
i Compar Swap Total
Step 4: Repeat while j>=0 && Value i son

a[j]>Temp 1 1 1 1+1=2
SET ARR[j+ 1] = ARR[j] 2 2 2 2+2=4
SET j = j- 1 3 3 3 3+3=6
[END OF INNER LOOP] … … … ----

Step 5: SET ARR[j + 1] = TEMP n-1 n-1 n-1 2n-2 2(n-1)

[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
i Compar Swap Total
Step 4: Repeat while j>=0 && Value i son

a[j]>Temp 1 1 1 1+1=2
SET ARR[j+ 1] = ARR[j] 2 2 2 2+2=4
SET j = j- 1 3 3 3 3+3=6 2(3)
[END OF INNER LOOP] ---- --- --- ---- ---

Step 5: SET ARR[j + 1] = TEMP n-1 n-1 n-1 2n-2 2(n-1)

[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
i Compar Swap Total
Step 4: Repeat while j>=0 && Value i son

a[j]>Temp 1 1 1 1+1=2
SET ARR[j+ 1] = ARR[j] 2 2 2 2+2=4 2(2)
SET j = j- 1 3 3 3 3+3=6 2(3)
[END OF INNER LOOP] ---- --- --- ---- ---

Step 5: SET ARR[j + 1] = TEMP n-1 n-1 n-1 2n-2 2(n-1)

[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
i Compar Swap Total
Step 4: Repeat while j>=0 && Value i son

a[j]>Temp 1 1 1 1+1=2 2(1)

SET ARR[j+ 1] = ARR[j] 2 2 2 2+2=4 2(2)
SET j = j- 1 3 3 3 3+3=6 2(3)
[END OF INNER LOOP] ---- --- --- ---- ---

Step 5: SET ARR[j + 1] = TEMP n-1 n-1 n-1 2n-2 2(n-1)

[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Worst
INSERTION-SORT (ARR, N) Case
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
i Comp Swap Total
Step 4: Repeat while j>=0 && Va lue a
rison
a[j]>Temp
1 1 1 1+1=2 2(1)
SET ARR[j+ 1] = ARR[j]
2 2 2 2+2=4 2(2)
SET j = j- 1
3 3 3 3+3=6 2(3)
[END OF INNER LOOP]
---- --- --- ---- ---
Step 5: SET ARR[j + 1] = TEMP n-1 n-1 n-1 2n-2 2(n-1)
[END OF LOOP]
= 2(1)+2(2)+2(3)+…
Step 6: EXIT +2(n-1)
= 2 (1+2+3+…+n)
=2 �
= n(n-1) =n2 - n
ANALYSIS OF INSERTION SORT
Time Complexity: Best Case
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1 i Value Comparison Swap

Step 4:Repeat while j>=0 &&

1
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Best Case
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1 i Value Comparison Swap

Step 4: Repeat while j>=0 &&

1 1 0
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Best Case
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1 i Value Comparison Swap

Step 4: Repeat while j>=0 &&

1 1 0
a[j]>Temp
2
SET ARR[j+ 1] = ARR[j]
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Best Case
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1 i Value Comparison Swap

Step 4: Repeat while j>=0 &&

1 1 0
a[j]>Temp
2 1 0
SET ARR[j+ 1] = ARR[j]
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Best Case
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1 i Value Comparison Swap

Step 4: Repeat while j>=0 &&

1 1 0
a[j]>Temp
2 1 0
SET ARR[j+ 1] = ARR[j]
3
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Best Case
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1 i Value Comparison Swap

Step 4: Repeat while j>=0 &&

1 1 0
a[j]>Temp
2 1 0
SET ARR[j+ 1] = ARR[j]
3 1 0
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Best Case
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1 i Value Comparison Swap

Step 4: Repeat while j>=0 &&

1 1 0
a[j]>Temp
2 1 0
SET ARR[j+ 1] = ARR[j]
3 1 0
SET j = j- 1
--- --- ---
[END OF INNER LOOP]
(n-1)
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
ANALYSIS OF INSERTION SORT
Time Complexity: Best Case
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1 i Value Comparison Swap

Step 4:Repeat while j>=0 &&

1 1 0
a[j]>Temp
2 1 0
SET ARR[j+ 1] = ARR[j]
3 1 0
SET j = j- 1
--- --- ---
[END OF INNER LOOP]
(n-1) 1 0
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP] So total (n-1) comparisons are
required
Step 6: EXIT
= Ω(n-1) = Ω(n)
ANALYSIS OF INSERTION SORT
Space Complexity
INSERTION-SORT (ARR, N)
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i]
• Insertion sort is an
Step 3: SET j= i- 1
in-place algorithm.
Step 4: Repeat while j>=0 && • It performs all computation
a[j]>Temp in the original array and
no other array is used.
SET ARR[j+ 1] = ARR[j] • Variables TEMP, i , j are
SET j = j- 1 required
[END OF INNER LOOP] for any input n
• Hence, the space
Step 5: SET ARR[j + 1] = TEMP
complexity works out to be O(1).
[END OF LOOP]
Step 6: EXIT
QUESTION ON INSERTION SORT
Time Complexity: Best Case
INSERTION-SORT (ARR, N)
0 1 2 3 4 5
Step 1: Repeat Steps 2 to 5 for i = 1 to N – 1
Step 2: SET TEMP = ARR[i] 2 3 4 6 8 9
Step 3: SET j= i- 1
Step 4: Repeat while j>=0 &&
a[j]>Temp
SET ARR[j+ 1] = ARR[j]
SET j = j- 1
[END OF INNER LOOP]
Step 5: SET ARR[j + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
• Write and illustrate an algorithm of Insertion
sort . Using it sort the element {19, 15, 18,
12}
 TOPICS TO BE
COVERED
1. Introductio
n
2. Recurrence
s
 TOPICS TO BE
COVERED
1. Recurrences
 Substitution Method
 Recursion Tree
Method
 Master Method
 RECURRENCES

 Recursive Program
 When function calls itself

A(n)
{
if( )
A(n/2) + A(n/2)
}

 To analyse complexity of recursive program we have to write

recursive function first and then by using substitution, recursion
tree, or master method calculate the complexity.
 RECURRENCES
 Recursive
function
A(n) T(n
{ )
if( )
A(n/2) +
A(n/2)
}
 Recursive
function
A(n) T(n
{ )
if( ) Compariso
A(n/2) + n
A(n/2)
Require Constant
}
Time

Additio
n
 RECURRENCES

 Recursive
function
A(n) T(n) =
{ C
if( ) Compariso
A(n/2) + n
A(n/2)
Require Constant
}
Time

Additio
n
 RECURRENCES

 Recursive
function
A(n) T(n) =
{ C
if( )
A(n/2) +
A(n/2)

T( )
}
𝑛

T( )
𝑛
2
2
 RECURRENCES
 Recursive
function

2
)
A(n) T(n) = C+ 2T
{ 𝑛
(
if( )
A(n/2) +
A(n/2)
}
 RECURRENCES
 Recursive
function

2
)
A(n) T(n) = C+ 2T Recursive
{ 𝑛 Function
(
if( )
A(n/2) +
A(n/2)
}
 RECURRENCES

Recursive
Function
Substitution M ethod

Recursion tree

M ethod M as te r

Method
 TOPICS TO BE
COVERED
1. Recurrences
 Substitution Method
 Recursion Tree
Method
 Master Method
 SUBSTITUTION METHOD
A(n) First find out recursive
{ function

if(n > 1 )
{
A(n-1)
}
}
 SUBSTITUTION METHOD

A(n) T(n) = C +
{ T(n-1)
if(n > 1 )
{
A(n-1)
}
}
 SUBSTITUTION METHOD

A(n) T(n) = C +
{ T(n-1)
if(n > 1 ) Back substitution method
{
A(n-1)
}
}
 SUBSTITUTION METHOD
A(n) T(n) = C +
{ T(n-1)
if(n > 1 ) Back substitution method
{
A(n-1)
} It can be applied to all type
} of problems

Slo
w
 SUBSTITUTION METHOD
A(n) T(n) = C +
{ T(n-1)
if(n > 1 ) Replace n by (n-
{
1)
A(n-1)
}
}
 SUBSTITUTION METHOD
A(n) T(n) = C +
{ T(n-1)
if( )
T(n-1) = C + T(n- Replace n by (n-
{
1-1) 1)
A(n-1)
}
}
 SUBSTITUTION METHOD
A(n) T(n) = C +
{ T(n-1)
if(n > 1 )
T(n-1) = C + Replace n by (n-
{
T(n-2) 1)
A(n-1)
}
}
 SUBSTITUTION METHOD
A(n) T(n) = C +
{ T(n-1)
if(n > 1 )
T(n-1) = C + Replace n by (n-
{
T(n-2) 1)
A(n-1)
} T(n-2) = C + Replace n by (n-
} T(n-3) 2)
 SUBSTITUTION METHOD
A(n) T(n) = C + T(n-1)
{ --- (1)
if(n > 1 ) T(n-1) = C + T(n-2)
{ --- (2)
A(n-1) T(n-2) = C + T(n-3) ---
} (3)
}
 SUBSTITUTION METHOD
A(n) T(n) = C + T(n-1)
{ --- (1)
if(n > 1 ) T(n-1) = C + T(n-2)
{ --- (2)
A(n-1) T(n-2) = C + T(n-3) ---
} (3)
}
Now substitute eqn2 in
eqn1
 SUBSTITUTION METHOD
A(n) T(n) = C T(n- ---
{ + 1) (1)
if(n > 1 )
{
A(n-1)
T(n-1) = C + T(n-2)
--- (2)
}
} T(n-2) = C + T(n-3) ---
(3)
Now substitute eqn2 in
eqn1
 SUBSTITUTION METHOD
A(n) T(n) = C + C + T(n-
{ 2)--- (1)
if(n > 1 )
{
A(n-1)
T(n-1) = C + T(n-2)
--- (2)
}
} T(n-2) = C + T(n-3) ---
(3)
Now substitute eqn2 in
eqn1
 SUBSTITUTION METHOD
A(n) T(n) = 2C+ T(n-2)---
{ (1)
if(n > 1 )
{
A(n-1)
T(n-1) = C + T(n-2)
--- (2)
}
} T(n-2) = C + T(n-3) ---
(3)
Now substitute eqn3 in
eqn1
 SUBSTITUTION METHOD
A(n) T(n) = 2C+ T(n-2)---
{ (1)
if(n > 1 )
{
A(n-1)
T(n-1) = C + T(n-2)
--- (2)
}
} T(n-2) = C + T(n-3) ---
(3)
Now substitute eqn3 in
eqn1
 SUBSTITUTION METHOD
A(n) T(n) = 2C+ C + T(n-
{ 3)--- (1)
if(n > 1 )
{
A(n-1)
T(n-1) = C + T(n-2)
--- (2)
}
} T(n-2) = C + T(n-3) ---
(3)
Now substitute eqn3 in
eqn1
 SUBSTITUTION METHOD
A(n) T(n) = 3C + T(n-
{ 3)--- (1)
if(n > 1 )
{ Like this it will go till k
A(n-1) number
}
}
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
if(n > 1 )
{ Like this it will go till k
A(n-1) number
}
} T(n) = kC +
T(n-k)
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
.
if(n > 1 ) .
.
{
T(n) = kC +
A(n-1) T(n-k)
} Now the next point is where to stop
So for this we have to find base
}
condition
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
.
if(n > 1 ) .
.
{
T(n) = kC +
A(n-1) T(n-k)
} The algorithm will execute when n is greater
than 1 It will stop when n becomes 1
}
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
.
if(n > 1 ) .
.
{
T(n) = kC +
A(n-1) T(n-k)
} T(n) = C + T(n-1)
for n>1
}
=1 for n=1
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
.
if(n > 1 ) .
.
{
T(n) = kC +
A(n-1) T(n-k)
} So this algorithm will stop when n-k =
1
}
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
.
if(n > 1 ) .
.
{
T(n) = kC +
A(n-1) T(n-k)
} So this algorithm will stop when n-k =
1
}
n-k =
1
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
.
if(n > 1 ) .
.
{
T(n) = kC +
A(n-1) T(n-k)
} So this algorithm will stop when n-k =
1
}
n-k =
1 k= n
-1
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
.
if(n > 1 ) .
.
{
T(n) = kC +
A(n-1) T(n-k)
} So this algorithm will stop when n-k =
1
}
n-k =
1 k= n
-1
Substitute k in equation
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
.
if(n > 1 ) ..
T(n) = kC +
{
T(n-k)
A(n-1)
}
}
 SUBSTITUTION METHOD
A(n) T(n) = 3C +
{ T(n-3)
.
if(n > 1 ) ..
T(n) = (n-1)C + T(n-
{
n-1)
A(n-1)
}
}
 SUBSTITUTION METHOD
A(n) T(n) = 3C + T(n-3)
.
{ .
.
if(n > 1 )
T(n) = (n-1)C + T(n-
{
n-1)
A(n-1)
} T(n) = (n-1)C + T(n-
}
n-1)
 SUBSTITUTION METHOD
A(n) T(n) = 3C + T(n-3)
.
{ .
.
if(n > 1 )
T(n) = (n-1)C + T(n-
{
n-1)
A(n-1)
} T(n) = (n-1)C + T(n-
}
n-1)
T(n) = (n-1)C + T(1)
 SUBSTITUTION METHOD
A(n) T(n) = 3C + T(n-3)
.
{ .
.
if(n > 1 )
T(n) = (n-1)C + T(n-
{
n-1)
A(n-1)
} T(n) = (n-1)C + T(n-
}
n-1)
T(n) = (n-1)C + T(1)

T(n) = (n-1)
 SUBSTITUTION METHOD
A(n) T(n) = 3C + T(n-3)
.
{ .
.
if(n > 1 )
T(n) = (n-1)C + T(n-
{
n-1)
A(n-1)
} T(n) = (n-1)C + T(n-
}
n-1)
T(n) = (n-1)C + T(1)

T(n) = (n-1)

T(n) = O(n)
 SUBSTITUTION METHOD

Example

T(n) = n + ;n>
T(n-1) 1
=1 ;n=
1
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
Substitute n by (n-
1)
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----(2)Substitute n by
T(n-2) (n-1)
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----(2)Substitute n by
T(n-2) (n-1)
T(n-2) = (n-2) + ----(3)Substitute n by
T(n-3) (n-2)
 SUBSTITUTION METHOD
T(n) = n + ;n> ---- T(n) = n +
T(n-1) 1 (1) T(n-1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
 SUBSTITUTION METHOD
T(n) = n + ;n> ---- T(n) = n T(n-
T(n-1) 1 (1) + 1)
=1 ;n= Substitute eqn (2) in eqn
1 (1)
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
 SUBSTITUTION METHOD
T(n) = n + ;n> ---- T(n) = n (n-1) + T(n-
T(n-1) 1 (1) + 2)
=1 ;n= Substitute eqn (2) in eqn
1 (1)
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
 SUBSTITUTION METHOD
T(n) = n + ;n> ---- T(n) = n + (n-1) +
T(n-1) 1 (1) T(n-2)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
 SUBSTITUTION METHOD
T(n) = n + ;n> ---- T(n) = n + (n- T(n-
T(n-1) 1 (1) 1) + 2)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
 SUBSTITUTION METHOD
T(n) = n + ;n> ---- T(n) = n + (n- (n-2) + T(n-
T(n-1) 1 (1) 1) + 3)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) +
T(n-3)
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) + T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-k)
+T(n-(k+1))
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) + T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-k)+T(n-(k+1))
We have to remove T(n-(k+1)) so by using base
condition
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) + T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-k)+T(n-(k+1))
We have to remove T(n-(k+1)) so by using base
condition
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) +
T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-k) n-(k+1) =
+T(n-(k+1)) 1
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) +
T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-k) n-(k+1) =
+T(n-(k+1)) 1
⸫ n-k-1 =
1
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) + T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-k) n-(k+1) =
+T(n-(k+1)) 1
⸫ n-k-1 =
1
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) + T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-k) n-(k+1) =
+T(n-(k+1)) 1
⸫ n-k-1 =
1
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) +
T(n-3) n-(k+1) =
T(n) = n + (n-1) + (n-2) + --- + (n-(n-2))+T(n-
((n-2)+1)) 1
⸫ n-k-1 =
1
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) + T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-(n-2))+T(n- n-(k+1) =
((n-2)+1)) 1
⸫ n-k-1 =
1
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) + T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-(n-
2))+T(1)
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) + T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-(n-
2))+T(1) T(n) = n + (n-1) + (n-2) + ---
+ 2+ 1
 SUBSTITUTION METHOD
T(n) = n + ;n> ----
T(n-1) 1 (1)
=1 ;n=
1
T(n-1) = (n-1) + ----
T(n-2) (2)

T(n-2) = (n-2) + ----

T(n-3) (3)
T(n) = n + (n-1) + (n-2) + T(n-3)
T(n) = n + (n-1) + (n-2) + --- + (n-(n-
2
𝑛 +𝑛
𝑛
2))+T(1)
= 2 22
T(n) = n + (n-1) + (n-2) + --- = =
𝑛+1
+ 2+ 1 O(n )
 TOPICS TO BE
1. Recurrences
COVERED
 Substitution Method
 Recursion Tree
Method
 Master Method
 RECURSION TREE METHOD
𝑛
2
T(n) = 2T( ;n>
= ) 1
+c c ;n=
1
 RECURSION TREE METHOD
𝑛
2
T(n) = 2T( ;n>
= ) 1
+c c ;n=
1 of work we can produce 2 problems
For doing ‘c’ amount
with
smaller set of inputs and each input size is reduced by
n/2
 RECURSION TREE METHOD
𝑛
2
T(n) = 2T( ;n>
= ) 1
+c c ;n=
1T(n)
 RECURSION TREE METHOD
𝑛
2
T(n) = 2T( ;n>
= ) 1
+c c ;n=
1 c
 RECURSION TREE METHOD
𝑛
2
T(n) = 2T( ;n>
= ) 1
+c c ;n=
1 c

T(n/2) T(n/2)
 RECURSION TREE METHOD
𝑛
2
T(n) = 2T( ;n>
= ) 1
+c c ;n=
1 c

c c
 RECURSION TREE METHOD
𝑛
2
T(n) = 2T( ;n>
= ) 1
+c c ;n=
1
c

c c

T(n/4 T(n/4) T(n/4) T(n/4)

 RECURSION TREE METHOD
𝑛
2
T(n) = 2T( ;n>
= ) 1
+c c ;n=
1 c

c c

(n/4) (n/4) (n/4 (n/4)

T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n> Total amount of work done at each
)
2
+c 1 level
;n=
=c
1 c

c c

(n/4) (n/4) (n/4 (n/4)

T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n> Total amount of work done at each
)
2
+c 1 level
;n=
=c
1 c C

c c

(n/4) (n/4) (n/4 (n/4)

T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n> Total amount of work done at each
)
2
+c 1 level
;n=
=c
1 c C

c c 2C

(n/4) (n/4) (n/4 (n/4)

T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n> Total amount of work done at each
)
2
+c 1 level
;n=
=c
1 c C

c c 2C

(n/4) (n/4) (n/4 (n/4) 4C

T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n> Total amount of work done at each
)
2
+c 1 level
;n=
=c
1 c C

c c 2C

(n/4) (n/4) (n/4 (n/4) 4C

nC

T(1
)
 𝑛 RECURSION TREE METHOD
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
1 c C

c c 2C

(n/4) (n/4) (n/4 (n/4) 4C

nC

T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
c 1 C
= c + 2c + 4c +
nc
c c 2C

(n/ (n/ (n/4 (n/ 4C

4) 4) 4)

nC

T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
c 1 C
= c + 2c + 4c + …
+ nc
c c 2C
= c (1 + 2 + 4 + ...
+ n)
(n/ (n/ (n/4 (n/ 4C
4) 4) 4)

nC

T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
c 1 C
= c + 2c + 4c + …
+ nc
c c 2C
= c (1 + 2 + 4 + ...
+ n)
(n/ (n/ (n/4 (n/ 4C
= c (1+ 2 + 4 + ... +
4) 4) 4)
n)

nC

T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
c 1 C
= c + 2c + 4c + … +
nc
c c 2C
= c (1 + 2 + 4 + ...
+ n)
(n/ (n/ (n/4 (n/ 4C
= c (1+ 2 + 4 + ... +
4) 4) 4)
n)

= 𝐜( 20 +21 + 22 + ⋯
+
nC

T(1 2𝑘 )
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
c 1 C
= c + 2c + 4c + … +
nc
c c 2C
= c (1 + 2 + 4 + ...
+ n)
(n/ (n/ (n/4 (n/ 4C
= c (1+ 2 + 4 + ... +
4) 4) 4)
n)

= 𝐜( 20 +21 + 22 + ⋯
+
nC

2𝑘 )
=c( 2𝑘+1 − 1)
T(1
)
 RECURSION TREE METHOD

𝑛
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
c 1 C
= c + 2c + 4c + … +
nc
c c 2C
= c (1 + 2 + 4 + ...
+ n)
(n/ (n/ (n/4 (n/ 4C
= c (1+ 2 + 4 + ... +
4) 4) 4)
n)

= 𝐜( 20 +21 + 22 + ⋯
+
nC

2𝑘 )
=c( 2𝑘+1 − 1)
T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
c 1 C
= c + 2c + 4c + … +
nc
c c 2C
= c (1 + 2 + 4 + ...
+ n)
(n/ (n/ (n/4 (n/ 4C
= c (1+ 2 + 4 + ... +
4) 4) 4)
n)

= 𝐜( 20 +21 + 22 + ⋯
+
nC

2𝑘 )
=c( 2𝑘+1 − 1)
T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
c 1 C
= c + 2c + 4c + … +
nc
c c 2C
= c (1 + 2 + 4 + ...
+ n)
(n/ (n/ (n/4 (n/ 4C
= c (1+ 2 + 4 + ... +
4) 4) 4)
n)

= 𝐜( 20 +21 + 22 + ⋯
+
nC

2𝑘 )
=c( 2𝑘+1 − 1)
T(1
)
 RECURSION TREE METHOD
𝑛
T(n) = 2T( ;n>
) Then add the total work done at each

2
+c 1 level
;n=
=c
c 1 C
= c + 2c + 4c + … +
nc
c c 2C
= c (1 + 2 + 4 + ...
+ n)
(n/ (n/ (n/4 (n/ 4C
= c (1+ 2 + 4 + ... +
4) 4) 4)
n)

= 𝐜( 20 +21 + 22 + ⋯
+
nC

2𝑘 )
=c( 2𝑘+1 − 1)
T(1
)
 TOPICS TO BE
1. Recurrences
COVERED
 Substitution Method
 Recursion Tree
Method
 Master Method
 TOPICS TO BE
COVERED
1. Recurrences
 Substitution Method
 Recursion Tree
Method
 Master Method
 MASTER METHOD
The master method provides a "cookbook" method for solving
recurrences of the form

𝑛
𝑇 𝑛 = 𝑎𝑇 +
𝑓 𝑛
�
�
where a ≥ 1 an d b > 1 are constants and f (n) is an asymptotically
positive
function

The recurrence describes the running ti me of an algorithm th at

divides a problem of size n into a subproblems, each of size n / b ,
where a an d b are positive constants. The a subproblems are
solved recursively, each in time T (n/b). The cost of dividing the
problem an d combining the results of the subproblems is described
by the function f(n).

The master method requires memori zati on of three cases, but

 MASTER METHOD
Master Theorem:

Let a ≥ 1 an d b > 1 be constants, let f (n) be a function, and let

T (n) be defi ned on the nonnegative integers by the recurrence
T(n) = aT ( n / b ) + f(n),
where we interpret n / b to me an either ⌊ n / b ⌋ or ⌈ n / b ⌉. Then T (n)
can be bounded asymptotically as follows.

1. If 𝑓 𝑛 = O 𝑛 log 𝑏 𝑎−𝛜 for some constant ϵ>0, = 𝜃 𝑛 log 𝑏

then 𝑇 𝑛 𝑎
2. If 𝑓 𝑛 = 𝜃 then 𝑇 𝑛 =𝜃
𝑛 lo g 𝑏 𝑎 lg 𝑛
3. If 𝑓 𝑛 = 𝑛 log 𝑏 𝑎 log 𝑏
𝛺 𝑛 for some constant ϵ > 0
𝑎𝑓 𝑛Τ𝑎+𝜖 𝑏 ≤ 𝑐𝑓 𝑛 for
and if
some constant c < 1 and all sufficiently large n, then 𝑇 𝑛 =
 MASTER METHOD

Master Theorem:

wi th the function 𝒏𝒍𝒐𝒈𝒃 𝒂, the solution to the recurrence is

In each of the three cases, we are comparing the function f (n)

determined by the larger of the two functions f(n) and 𝑛 lo g 𝑏 𝑎

1, the function 𝑛 lo g 𝑏 𝑎

solution is 𝑇
 If, as in case is the larger th an f(n) , then
= 𝜃
𝑛
the
 If, as in case 𝑛 log
3, the𝑏 𝑎 function f (n) is the larger th an 𝑛 lo g 𝑏 𝑎 ,
then the
solution is T (n) = θ(f (n)).

 If, as in case 2, the two functions are the same size, we

multiply by a logarithmic factor, and the solution is
𝑇 𝑛 = 𝜃 𝑛 log 𝑏 𝑎 lg 𝑛 = θ(f (n) lg 𝑛)
 MASTER METHOD

Master Theorem:
(example-1)

𝐓 𝐧 = 𝟗𝐓 𝐧Τ𝟑+ 𝐧
 MASTER METHOD
Master Theorem:
(example-1)

𝐓 𝐧 = 𝟗𝐓 𝐧Τ𝟑+ 𝐧

𝐜𝐨𝐦𝐩𝐚𝐫𝐞 𝐰ⅈ𝐭𝐡 𝐦𝐚𝐬𝐭𝐞𝐫𝐬

𝐞𝐪𝐮𝐚𝐭ⅈ𝐨𝐧
 MASTER METHOD
Master Theorem:
(example-1)

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑 +𝐧

T(n) = a T(n/b) + f(n),

Master Theorem: MASTER METHOD
(example-1)

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑 +𝐧

T(n) = a T(n/b) +

f(n), a = 9 , b =

3, f(n) = n
 MASTER METHOD

Master Theorem:
for some constant ϵ>0, then 𝑇
𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑
(example-1)
= O 𝑛 log 𝑏
𝑓 𝑛 𝑛 =
1. If

+𝐧
𝑎−𝛜
𝜃

T(n) = a T(n/b) + 𝑛 log 𝑏 𝑎

=𝜃 then 𝑇 𝑛 = 𝜃 𝑛 log 𝑏 𝑎
f(n), 𝑓 𝑛 lg 𝑛
2. If

3. If 𝑓 𝑛 = 𝛺 𝑛 log 𝑏 for some constant ϵ > 0

a = 9 , b = 3,
𝑛 log 𝑏 𝑎

𝑎𝑓 𝑛Τ𝑏≤ 𝑐𝑓 𝑛
f(n) = n
a n d if 𝑎+𝜖

for some constant c 1 and all sufficiently

large n, then
𝑇 𝑛 = 𝜃𝑓 𝑛
 MASTER METHOD
Master Theorem:

for some constant ϵ>0,

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑
(example-1)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝐧 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
f(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 9 , b = 3, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = n if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
and
𝐧 constant c 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

large n, then
𝑇 𝑛 = 𝜃𝑓 𝑛
 MASTER METHOD
Master Theorem:

for some constant ϵ>0,

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑
(example-1)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝐧 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
f(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 9 , b = 3, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = n if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
and
𝐧 constant c 1 and all sufficiently
𝒇𝒊𝒏𝒅
𝐥𝐨𝐠 𝐚+𝛜
for some
𝐛

large n, then
𝐧𝐥𝐨𝐠𝐛 𝐚 𝑇 𝑛 = 𝜃𝑓 𝑛
 MASTER METHOD
Master Theorem:

for some constant ϵ>0,

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑
(example-1)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝐧 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
f(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 9 , b = 3, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = n if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
and
𝐧 constant c < 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 = large n, then

𝑇 𝑛 = 𝜃𝑓 𝑛
𝐧𝐥𝐨𝐠𝟑 𝟗
 MASTER METHOD
Master Theorem:

for some constant ϵ>0,

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑
(example-1)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝐧 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
f(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 9 , b = 3, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = n if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 =
and
𝐧 constant c < 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

large n, then
𝐧𝟐 𝑇 𝑛 = 𝜃𝑓 𝑛
 MASTER METHOD

Master Theorem:

for some constant ϵ>0,

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑
(example-1)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝐧 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
f(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 9 , b = 3, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = n if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 =
and
𝐧 constant c < 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

large n, then
𝐧𝟐 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝐧𝐥𝐨𝐠𝐛 𝐚
is larger than
f(n)
 MASTER METHOD
Master Theorem:
for some constant ϵ>0,
𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑
(example-1)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝐧 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
f(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 9 , b = 3, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = n if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 =
and
𝐧 constant c < 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

large n, then
𝐧𝟐 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝐧𝐥𝐨𝐠𝐛 𝐚
is larger than

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟏 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
 MASTER METHOD
Master Theorem:

for some constant ϵ>0,

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑
(example-1)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

+𝐧
𝐚−𝝐
= 𝛉
𝐧
T(n) = a T(n/b) +
then
𝒏𝒍𝒐𝒈𝒃 𝒂 then 𝑇 𝑛 =𝜃
f(n), 𝑓 𝑛
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑛 log 𝑏 𝑎 lg 𝑛
2. If
𝐚
a = 9 , b = 3, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = n if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 =
and
𝐧 𝐥𝐨𝐠𝐛 𝐚+𝛜
for some constant c < 1 and all sufficiently
large n, then
𝐧𝟐 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝐧𝐥𝐨𝐠𝐛 𝐚
is larger than

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟏 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
 MASTER METHOD
Master Theorem:

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑 for some constant ϵ>0,

(example-1)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
+𝐧
1. If
𝐚−𝝐
= 𝛉
T(n) = a T(n/b) + 𝐧 then

f(n), = 𝜃 𝐧𝐥𝐨𝐠𝐛 then 𝑇 𝑛

𝒏𝒍𝒐𝒈 =𝜃
𝒃 𝒂

𝑓 𝑛 𝑛 log 𝑏 𝑎 lg 𝑛
2. If

a = 9 , b = 3,
𝐚
3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = n if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 =
and
𝐧 𝐥𝐨𝐠𝐛 𝐚+𝛜
for some constant c < 1 and all sufficiently

𝐧𝟐
large n, then

𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝑇 𝑛 = 𝜃𝑓 𝑛

𝐧𝐥𝐨𝐠𝐛 𝐚
is larger than

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟏 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:

for some constant ϵ>0,

𝐓 𝐧 = 𝟗 𝐓 𝐧Τ𝟑
(example-1)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

+𝐧
𝐚−𝝐
= 𝛉
𝐧
T(n) = a T(n/b) +
then
𝒏𝒍𝒐𝒈𝒃 𝒂 then 𝑇 𝑛 =𝜃
f(n), 𝑓 𝑛
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑛 log 𝑏 𝑎 lg 𝑛
2. If
𝐚
a = 9 , b = 3, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = n if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 =
and
𝐧 𝐥𝐨𝐠𝐛 𝐚+𝛜
for some constant c < 1 and all sufficiently
large n, then
𝐧𝟐 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝐧𝐥𝐨𝐠𝐛 𝐚
is larger than

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟏 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
(example-2)

𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑 +𝟏
Master Theorem:
(example-2) MASTER METHOD

𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑 +𝟏

𝐜𝐨𝐦𝐩𝐚𝐫𝐞 𝐰ⅈ𝐭𝐡 𝐦𝐚𝐬𝐭𝐞𝐫𝐬

𝐞𝐪𝐮𝐚𝐭ⅈ𝐨𝐧
Master Theorem:
(example-2) MASTER METHOD

𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑 +𝟏

T(n) = a T(n/b) + f (n),

Master Theorem:
(example-2) MASTER METHOD

𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑 +𝟏

T(n) = a T(n/b) + f (n),

a = 1 , b = 3/2, f(n) = 1
Master Theorem:
MASTER METHOD
for some constant ϵ>0, then 𝑇
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= O 𝑛 log 𝑏
𝑓 𝑛 𝑛 =
1. If

+𝟏
𝑎−𝛜
𝜃

𝑛 log 𝑏 𝑎
=𝜃 then 𝑇 𝑛 = 𝜃 𝑛 log 𝑏 𝑎
𝑓 𝑛 lg 𝑛
2. If

T(n) = a T(n/b) + f 3. If 𝑓 𝑛 = 𝛺 𝑛 log 𝑏 for some constant ϵ > 0

(an),
= 1 , b = 3/2,
𝑛 log 𝑏 𝑎

𝑎𝑓 𝑛Τ𝑏≤ 𝑐𝑓 𝑛
f(n) = 1
a n d if 𝑎+𝜖

for some constant c 1 and all sufficiently

large n, then
𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝟏 𝑇 𝑛
= 𝜃 𝐚−𝝐

then 𝑇 𝑛 =𝜃
then
2. If 𝑛 log 𝑏 𝑎
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝑛 log 𝑏 𝑎 lg 𝑛
T(n) = a T(n/b) + f 𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
and
𝐧 constant c 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

large n, then
𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝟏 𝑇 𝑛
= 𝜃 𝐚−𝝐

then 𝑇 𝑛 =𝜃
then
2. If 𝑛 log 𝑏 𝑎
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝑛 log 𝑏 𝑎 lg 𝑛
T(n) = a T(n/b) + f 𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
and
𝐧 constant c 1 and all sufficiently
𝒇𝒊𝒏𝒅
𝐥𝐨𝐠 𝐚+𝛜
for some
𝐛

large n, then
𝐧𝐥𝐨𝐠𝐛 𝐚 𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If the

+𝟏 𝑇 𝑛
= 𝜃 𝐚−𝝐
ϵ>0, n

= 𝜃 𝐧𝐥𝐨𝐠𝐛 then 𝑇 𝑛= 𝜃 𝑛
2. If 𝑛 log 𝑏 𝑎 log 𝑏 𝑎

𝑓 𝑛 lg 𝑛
T(n) = a T(n/b) + f 𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏

𝒇𝒊𝒏𝒅 𝐥𝐨𝐠
𝐧�
for some constant
𝐛 𝐚+𝛜 c < 1 and all sufficiently
and
𝐧𝐥𝐨𝐠
𝐥𝐨𝐠𝟑/𝟐 large n, then
𝐚 � 𝑐𝑓 𝑛
= 𝐧
≤

𝟏 𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If the

+𝟏 𝑇 𝑛
= 𝜃 𝐚−𝝐
ϵ>0, n

= 𝜃 𝐧𝐥𝐨𝐠𝐛 then 𝑇 𝑛= 𝜃 𝑛
2. If 𝑛 log 𝑏 𝑎 log 𝑏 𝑎

𝑓 𝑛 lg 𝑛
T(n) = a T(n/b) + f 𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏

𝒇𝒊𝒏𝒅 𝐥𝐨𝐠𝐛 =
for some constant
𝐛 𝐚+𝛜 c < 1 and all sufficiently
and
𝐧𝐥𝐨𝐠
� large n, then

𝐧
𝑐𝑓 𝑛
≤

𝐚 𝒏
� 𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝟏 𝑇 𝑛
= 𝜃 𝐚−𝝐

then 𝑇 𝑛 =𝜃
then
2. If 𝑛 log 𝑏 𝑎
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝑛 log 𝑏 𝑎 lg 𝑛
T(n) = a T(n/b) + f 𝐚

(an)= 1 , b = 3/2,
3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛

𝒇𝒊𝒏𝒅 𝐥𝐨𝐠𝐛 = 𝒏��

and
𝐧 constant c < 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

𝐧
large n, then
𝐚 =𝟏 𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝟏 𝑇 𝑛
= 𝜃 𝐚−𝝐

then 𝑇 𝑛 =𝜃
then
2. If 𝑛 log 𝑏 𝑎
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝑛 log 𝑏 𝑎 lg 𝑛
T(n) = a T(n/b) + f 𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛

𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 ��
and
𝐧 constant c < 1 and all sufficiently
𝐥𝐨𝐠 𝐚+𝛜

=𝒏
for some
𝐛

large n, then
𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
=𝟏
𝐧𝐥𝐨𝐠𝐛 𝐚
is equal to
f(n)
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

+𝟏 𝑇 𝑛
= 𝜃 𝐚−𝝐

then 𝑇 𝑛 =𝜃
then
2. If 𝑛 log 𝑏 𝑎
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝑛 log 𝑏 𝑎 lg 𝑛
T(n) = a T(n/b) + f 𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛

𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 ��
and
𝐧 constant c < 1 and all sufficiently
𝐥𝐨𝐠 𝐚+𝛜

=𝒏
for some
𝐛

large n, then
𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
= 𝐥𝐨𝐠
𝟏 𝐚
𝐧 𝐛
is equal to

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟐 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

+𝟏
𝐚−𝝐
= 𝛉
𝐧 then
𝒏𝒍𝒐𝒈𝒃 𝒂
= 𝛉 𝐧𝐥𝐨𝐠𝐛
𝐭𝐡𝐞𝐧 𝐓 𝐧 =
𝐟 𝐧
T(n) = a T(n/b) + f 𝛉 𝐧𝐥𝐨𝐠𝐛 𝐚 𝐥𝐠 𝐧
2. If
𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐥𝐨𝐠𝐛 = 𝒏��
and
𝐧 𝐥𝐨𝐠𝐛 𝐚+𝛜
for some constant c < 1 and all sufficiently

𝐧
large n, then
𝐚 =𝟏 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝐧𝐥𝐨𝐠𝐛 𝐚
is equal to

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟐 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

+𝟏
𝐚−𝝐
= 𝛉
𝐧 then
𝒏𝒍𝒐𝒈𝒃 𝒂
= 𝛉 𝐧𝐥𝐨𝐠𝐛
𝐭𝐡𝐞𝐧 𝐓 𝐧 =
𝐟 𝐧
T(n) = a T(n/b) + f 𝛉 𝐧𝐥𝐨𝐠𝐛 𝐚 𝐥𝐠 𝐧
2. If
𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐥𝐨𝐠𝐛 = 𝒏��
and
𝐧 𝐥𝐨𝐠𝐛 𝐚+𝛜
for some constant c < 1 and all sufficiently

𝐧
large n, then
𝐚 =𝟏 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝐧𝐥𝐨𝐠𝐛 𝐚
is equal to

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟐 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

+𝟏
𝐚−𝝐
= 𝛉
𝐧 then
𝒏𝒍𝒐𝒈𝒃 𝒂
= 𝛉 𝐧𝐥𝐨𝐠𝐛
𝐭𝐡𝐞𝐧 𝐓 𝐧 =
𝐟 𝐧
T(n) = a T(n/b) + f 𝛉 𝐧𝐥𝐨𝐠𝐛 𝐚 𝐥𝐠 𝐧
2. If
𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐥𝐨𝐠𝐛 = 𝒏��
and
𝐧 𝐥𝐨𝐠𝐛 𝐚+𝛜
for some constant c < 1 and all sufficiently

𝐧
large n, then
𝐚 =𝟏 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝐧𝐥𝐨𝐠𝐛 𝐚
is equal to

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟐 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

+𝟏
𝐚−𝝐
= 𝛉
𝐧 then
𝒏𝒍𝒐𝒈𝒃 𝒂
= 𝛉 𝐧𝐥𝐨𝐠𝐛
𝐭𝐡𝐞𝐧 𝐓 𝐧 =
𝐟 𝐧
T(n) = a T(n/b) + f 𝛉 𝐧𝐥𝐨𝐠𝐛 𝐚 𝐥𝐠 𝐧
2. If
𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐥𝐨𝐠𝐛 = 𝒏��
and
𝐧 𝐥𝐨𝐠𝐛 𝐚+𝛜
for some constant c < 1 and all sufficiently

𝐧
large n, then
𝐚 =𝟏 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝐧𝐥𝐨𝐠𝐛 𝐚
is equal to

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟐 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝑻 𝟐 𝒏Τ𝟑
(example-2)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

+𝟏
𝐚−𝝐
= 𝛉
𝐧 then
𝒏𝒍𝒐𝒈𝒃 𝒂
= 𝛉 𝐧𝐥𝐨𝐠𝐛
𝐭𝐡𝐞𝐧 𝐓 𝐧 =
𝐟 𝐧
T(n) = a T(n/b) + f 𝛉 𝐧𝐥𝐨𝐠𝐛 𝐚 𝐥𝐠 𝐧
2. If
𝐚

(an),
= 1 , b = 3/2, 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
f(n) = 1 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅 𝐥𝐨𝐠𝐛 = 𝒏��
and
𝐧 𝐥𝐨𝐠𝐛 𝐚+𝛜
for some constant c < 1 and all sufficiently

𝐧
large n, then
𝐚 =𝟏 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏
𝐧𝐥𝐨𝐠𝐛 𝐚
is equal to

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟐 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

f(n)

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
(example-3) MASTER METHOD

𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏 𝐥𝐠 𝒏
Master Theorem:
(example-3) MASTER METHOD

𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏 𝐥𝐠 𝒏

𝐜𝐨𝐦𝐩𝐚𝐫𝐞 𝐰ⅈ𝐭𝐡 𝐦𝐚𝐬𝐭𝐞𝐫𝐬

𝐞𝐪𝐮𝐚𝐭ⅈ𝐨𝐧
Master Theorem:
(example-3) MASTER METHOD

𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏 𝐥𝐠 𝒏

T(n) = a T(n/b) + f (n),

Master Theorem:
(example-3) MASTER METHOD

𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏 𝐥𝐠 𝒏

T(n) = a T(n/b) + f (n),

a = 3 , b = 4 , f(n) = 𝒏 𝐥𝐠 𝒏
Master Theorem:
MASTER METHOD
for some constant ϵ>0, then 𝑇
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= O 𝑛 log 𝑏
𝑓 𝑛 𝑛 =
1. If

𝐥𝐠 𝒏
𝑎−𝛜
𝜃

T(n) = a T(n/b) + f 2. 𝑛 Iflog 𝑏 𝑎 = 𝜃 then 𝑇 𝑛 = 𝜃 𝑛 log 𝑏 𝑎

(n), 𝑓 𝑛 lg 𝑛
3. If 𝑓 𝑛 = 𝛺 𝑛 log 𝑏 for some constant ϵ > 0
a = 3 , b = 4 , f(n)
𝑛 log 𝑏 𝑎

𝑎𝑓 𝑛Τ𝑏≤
= 𝒏 𝐥𝐠 𝒏
𝑎+𝜖
for some constant c 1 and all sufficiently
a n d if
𝑐𝑓 𝑛
large n, then
𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

𝐥𝐠 𝒏 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + f then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 3 , b = 4 , f(n) 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
and
𝐧 constant c 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

large n, then
𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

𝐥𝐠 𝒏 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + f then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 3 , b = 4 , f(n) 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛
𝒇𝒊𝒏𝒅
and
𝐧 constant c 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

large n, then
𝐧𝐥𝐨𝐠𝐛 𝐚 𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

𝐥𝐠 𝒏 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + f then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 3 , b = 4 , f(n) 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛

𝒇𝒊𝒏𝒅 𝐥𝐨𝐠𝐧 𝐛𝐚
and
𝐧 constant c < 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

= 𝐧
large n, then
𝐥𝐨𝐠𝟒 𝟑 𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

𝐥𝐠 𝒏 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + f then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 3 , b = 4 , f(n) 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛

𝒇𝒊𝒏𝒅
and
𝐧 constant c < 1 and all sufficiently
𝐥𝐨𝐠 𝐚+𝛜
𝐥𝐨𝐠 = 𝟎.𝟕𝟗 for some
𝐛

𝐧
𝟑 large n, then
𝐚 𝒏 𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

𝐥𝐠 𝒏 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + f then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 3 , b = 4 , f(n) 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛

𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 𝟎.𝟕𝟗

and
𝐧 constant c < 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

𝟑 large n, then
=𝒏 𝑇 𝑛 = 𝜃𝑓 𝑛
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

𝐥𝐠 𝒏 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + f then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 3 , b = 4 , f(n) 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛

𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 𝟎.𝟕𝟗

and
𝐧 constant c < 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

𝟑 large n, then
=𝒏 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏f(n) ⅈ𝐬 𝐥𝐚𝐫𝐠𝐞𝐫
𝐭𝐡𝐚𝐧 𝐧𝐥𝐨𝐠𝐛 𝐚
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛
1. If

𝐥𝐠 𝒏 𝑇 𝑛
= 𝜃 𝐚−𝝐

T(n) = a T(n/b) + f then 𝑇 𝑛 =𝜃

then
2. If 𝑛 log 𝑏 𝑎
(n),
= 𝜃 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛 𝐚 𝑛 log 𝑏 𝑎 lg 𝑛
a = 3 , b = 4 , f(n) 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛

𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 𝟎.𝟕𝟗

and
𝐧 constant c < 1 and all sufficiently
for some
𝐥𝐨𝐠𝐛 𝐚+𝛜

𝟑 large n, then
=𝒏 𝑇 𝑛 = 𝜃𝑓 𝑛
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏f(n) ⅈ𝐬 𝐥𝐚𝐫𝐠𝐞𝐫 𝐭𝐡𝐚𝐧 𝐧𝐥𝐨𝐠𝐛 𝐚
𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟑 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆
𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

𝐥𝐠 𝒏
𝐚−𝝐
= 𝛉
𝐧
T(n) = a T(n/b) + f
then
𝒏𝒍𝒐𝒈𝒃 𝒂 𝐭𝐡𝐞𝐧 𝐓 𝐧 =
(n), 𝐟 𝐧
= 𝛉 𝐧𝐥𝐨𝐠𝐛
𝛉 𝐧𝐥𝐨𝐠𝐛 𝐚 𝐥𝐠 𝐧
2. If
𝐚
a = 3 , b = 4 , f(n) 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛 for some

𝒇𝒊𝒏𝒅 𝐧
and
𝐧c <
𝐥𝐨𝐠 𝐚+𝛜
𝐥𝐨𝐠𝐛 𝐚 = 𝒏𝟎.𝟕𝟗𝟑 constant
𝐛

1 and all sufficiently large n, then

𝑇 𝑛 = 𝜃𝑓
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏f(n) ⅈ𝐬 𝐥𝐚𝐫𝐠𝐞𝐫
𝑛 𝐭𝐡𝐚𝐧 𝐧𝐥𝐨𝐠𝐛 𝐚
𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟑 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆
𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
MASTER METHOD
for some constant ϵ>0,
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

𝐥𝐠 𝒏
𝐚−𝝐
= 𝛉
𝐧
T(n) = a T(n/b) + f
then
𝒏𝒍𝒐𝒈𝒃 𝒂 𝐭𝐡𝐞𝐧 𝐓 𝐧 =
(n), 𝐟 𝐧
= 𝛉 𝐧𝐥𝐨𝐠𝐛
𝛉 𝐧𝐥𝐨𝐠𝐛 𝐚 𝐥𝐠 𝐧
2. If
𝐚
a = 3 , b = 4 , f(n) 3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛 for some

𝒇𝒊𝒏𝒅 𝐧
and
𝐧c <
𝐥𝐨𝐠 𝐚+𝛜
𝐥𝐨𝐠𝐛 𝐚 = 𝒏𝟎.𝟕𝟗𝟑 constant
𝐛

1 and all sufficiently large n, then

𝑇 𝑛 = 𝜃𝑓
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏f(n) ⅈ𝐬 𝐥𝐚𝐫𝐠𝐞𝐫
𝑛 𝐭𝐡𝐚𝐧 𝐧𝐥𝐨𝐠𝐛 𝐚
𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟑 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆
𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔
Master Theorem:
MASTER METHOD
𝐓 𝐧 = 𝟑𝑻 𝒏Τ𝟒+ 𝒏 for some constant ϵ>0,
(example-3)
= 𝐎 𝐧𝐥𝐨𝐠𝐛
𝑓 𝑛𝐓
1. If

𝐥𝐠 𝒏 = 𝛉
𝐚−𝝐

T(n) = a T(n/b) + f 𝐧 then

𝐭𝐡𝐞𝐧 𝐓 𝐧 =
(n),
𝒏𝒍𝒐𝒈𝒃 𝒂
= 𝛉 𝐧𝐥𝐨𝐠𝐛
𝐟 𝐧 𝛉 𝐧𝐥𝐨𝐠𝐛 𝐚 𝐥𝐠 𝐧
2. If

a = 3 , b = 4 , f(n)
𝐚
3. If 𝑓 𝑛 = 𝛺 for some constant ϵ > 0
= 𝒏 𝐥𝐠 𝒏 if 𝑎𝑓 𝑛Τ𝑏 ≤ 𝑐𝑓 𝑛 for some
𝒇𝒊𝒏𝒅 𝐧𝐥𝐨𝐠𝐛 𝐚 =
and
𝐧c <
constant
𝐥𝐨𝐠𝐛 𝐚+𝛜

1 and all sufficiently large n, then

𝒏𝟎.𝟕𝟗𝟑 𝑇 𝑛 = 𝜃𝑓
𝒕𝒉𝒆 𝒇𝒖𝒏𝒄𝒕𝒊𝒐𝒏f(n) ⅈ𝐬 𝐥𝐚𝐫𝐠𝐞𝐫
𝑛 𝐭𝐡𝐚𝐧 𝐧 𝐥𝐨𝐠 𝐛 𝐚

𝒔𝒐 𝒘𝒆 𝒄𝒂𝒏 𝒂𝒑𝒑𝒍𝒚 𝒄𝒂𝒔𝒆 − 𝟑 𝒂𝒏𝒅 𝒄𝒐𝒏𝒄𝒍𝒖𝒅𝒆

𝒕𝒉𝒂𝒕 𝒔𝒐𝒍𝒖𝒕𝒊𝒐𝒏 𝒊𝒔