School of Computer Science and Engineering

Design and Analysis of Algorithm [R1UC407B]

Module-I: Introduction
Dr. A K Yadav

School of Computer Science and Engineering

Plat No 2, Sector 17A, Yamuna Expressway
Greater Noida, Uttar Pradesh - 203201

February 12, 2025

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 1/87

 School of Computer Science and Engineering

Contents
Introduction to algorithms 3
Asymptotic notations 7
Relationship between notations 11
Recurrences 20
Recurrence Solution Methods 21
Substitution method 22
Iteration method 34
Recursion tree method 50
Master method (D&C) 58
Muster Theorem (S&C) 70
Complexity Analysis 80
Complexity analysis: Insertion sort 82

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 2/87

 School of Computer Science and Engineering

Introduction to algorithms
▶ What is an algorithm?
- An algorithm is a set of rules for carrying out calculation
either by hand or on a machine.
- An algorithm is a sequence of computational steps that
transform the input into output.
- An algorithm is a sequence of operations performed on data
that have to be organized in data structures.
- A finite set of instructions that specify a sequence of
operations to be carried out in order to solve a specific
problem or class of problems.
- An algorithm is an abstraction of a program to be executed
on a physical machine.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 3/87

 School of Computer Science and Engineering

- An algorithm is any well-defined computational procedure

that takes some value, or set of values, as input and produces
some value, or set of values, as output.
▶ Why do we study algorithms?
- To make solution more faster.
- To compare performance as a function of input size.
▶ Properties
- Finiteness
- Unambiguous
- Sequence of execution
- Input/output
- Feasible

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 4/87

 School of Computer Science and Engineering

▶ Algoritm vs Program
- Algorithm is independent of programming language and
written in any natural language.
- Implementation of any algorithm in a programming language
is a program.
▶ Design Techniques
- Divide and Conquer (D&C)
- Dynamic Programming (DP)
- Greedy Approach
- Branch and Bound
- Backtracking
- Randomized

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 5/87

 School of Computer Science and Engineering

▶ Random Access Machine (RAM)

- Simply count primitive operations
- Use pseudo code
- Independent of programming language
- Equal time for all operations

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 6/87

 School of Computer Science and Engineering

Asymptotic notations
1. O - notation ”Big O” : Asymptotic upper bound,
O(g(n)) = {f (n) : ∃c, n0 > 0 such that 0 ≤ f (n) ≤
cg(n) for all n ≥ n0 }
f (n) ∈ O(g(n))
f (n) = O(g(n))

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 7/87

 School of Computer Science and Engineering

2. Ω - notation ”Big omega” : Asymptotic lower bound,

Ω(g(n)) = {f (n) : ∃c, n0 > 0 such that 0 ≤ cg(n) ≤
f (n) for all n ≥ n0 }
f (n) ∈ Ω(g(n))
f (n) = Ω(g(n))

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 8/87

 School of Computer Science and Engineering

3. Θ - notation : Asymptotic tight bound,

Θ(g(n)) = {f (n) : ∃c1 , c2 , n0 > 0 such that 0 ≤ c1 g(n) ≤
f (n) ≤ c2 g(n) for all n ≥ n0 }
f (n) ∈ Θ(g(n))
f (n) = Θ(g(n))

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 9/87

 School of Computer Science and Engineering

4. o - notation ”small o”: Asymptotic loose upper bound,

o(g(n)) = {f (n) : ∀c > 0, ∃n0 such that 0 ≤ f (n) <
cg(n) for all n ≥ n0 }
5. ω - notation ”small omega”: Asymptotic loose lower bound,
ω(g(n)) = {f (n) : ∀c > 0, ∃n0 such that 0 ≤ cg(n) <
f (n) for all n ≥ n0 }
Benefits of Asymptotic Notations:
- Simple representation of algorithm efficiency.
- Easy comparison of performance of algorithms.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 10/87

 School of Computer Science and Engineering

Relationship between notations

▶ f (n) = Θ(g(n)) ⇒ f (n) = O(g(n))
▶ f (n) = Θ(g(n)) ⇒ f (n) = Ω(g(n))
▶ f (n) = O(g(n))&f (n) = Ω(g(n)) ⇒ f (n) = Θ(g(n))
▶ f (n) = O(g(n)) may or may be tight upper bound but
f (n) = o(g(n)) is always upper loose bound and
o(g(n)) ∈ O(g(n)) and o(g(n)) ⊂ O(g(n))
▶ f (n) = Ω(g(n)) may or may be tight lower bound but
f (n) = ω(g(n)) is always lower loose bound and
ω(g(n)) ∈ Ω(g(n)) and ω(g(n)) ⊂ Ω(g(n))

0
f (n) = o(g(n))


f (n)
▶ lim = ∞ f (n) = ω(g(n))
n→∞ g(n) 
0 < c < ∞, f (n) = Θ(g(n))

c

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 11/87

 School of Computer Science and Engineering
d
X
▶ Let f (n) = ai ni where ad > 0, is a degree-d polynomial in
i=0
n and k is a constant then:
- if k ≥ d, then f (n) = O(nk ).
- if k ≤ d, then f (n) = Ω(nk ).
- if k = d, then f (n) = Θ(nk ).
- if k > d, then f (n) = o(nk ).
- if k < d, then f (n) = ω(nk ).

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 12/87

 School of Computer Science and Engineering

Examples
1. Show that an + b = O(n2 )
2. Show that 21 n2 − 3n = Θ(n2 )
3. Show that 12 n2 − 3n = Ω(n)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 13/87

 School of Computer Science and Engineering

Solutions
1. Show that an + b = O(n2 )

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 14/87

 School of Computer Science and Engineering

we have to prove that an + b ≤ cn2 for some positive

constants c, n0 and for all n ≥ n0 .

an + b ≤ an + |b| for all n ≥ 1

≤ an + |b|n for all n ≥ 1
= (a + |b|)n
= cn where c = a + |b|
≤ cn2
⇒ an + b ≤ cn2 where c = a + |b| > 0 all n ≥ n0 = 1
∴ an + b = O(n2 )
⇒ an + b < cn2 for all c > 0 all n > n0 = max (1, −b/a)
∴ an + b = o(n2 )

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 15/87

 School of Computer Science and Engineering

2. Show that 21 n2 − 3n = Θ(n2 )

We have to prove that c1 n2 ≤ 12 n2 − 3n ≤ c2 n2 for some
positive constants c1 , c2 , n0 and for all n ≥ n0 .

1
c1 n2 ≤ n2 − 3n ≤ c2 n2
2
1 3
⇒ c1 ≤ − ≤ c2 after dividing n2
2 n
1 3
⇒ 0 < c1 ≤ −
2 n
1 3
⇒0< −
2 n
3 1
⇒ <
n 2

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 16/87

 School of Computer Science and Engineering

⇒n>6
Let n = 7
1
⇒ 0 < c1 ≤
14
1
Let c1 =
14
1 3
Now 0 < − ≤ c2
2 n
1
⇒ 0 < ≤ c2 when n = ∞
2
1
Let c2 =
2
1 2
⇒ 0 < 14 n ≤ 12 n2 − 3n ≤ 21 n2 for all n ≥ n0 = 7 and any
1
constant 0 < c1 ≤ 14 ≤ 12 ≤ c2 .

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 17/87

 School of Computer Science and Engineering

3. Show that 21 n2 − 3n = Ω(n)

We have to prove that cn ≤ 12 n2 − 3n for some positive
constants c, n0 and for all n ≥ n0 .

1
Let cn ≤ n2 − 3n
2
1
c ≤ n − 3 after dividing n both side
2
1
⇒c ≤ n+3
2
1
⇒ c ≤ n + 3n for all n > 0
2
7
⇒c≤ n
2

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 18/87

 School of Computer Science and Engineering
7 7
⇒ ≤ n for all n ≥ 1
2 2
7
∴c≤
2
7
Let c =
2
⇒ 72 n ≤ 12 n2 − 3n for all positive constants c ≤ 7
2 and for all
n ≥ n0 = 1.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 19/87

 School of Computer Science and Engineering

Recurrences
A recurrence is an equation or inequality that describes a function
in terms of its value on smaller inputs.

(
nf (n − 1) if n > 1
f (n) =
1 if n = 1

(
2T (n/2) + Θ(n) if n > 1
T (n) =
Θ(1) if n = 1

(
T (n − 1) if n > 1
T (n) =
Θ(1) if n = 1

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 20/87

 School of Computer Science and Engineering

How to solve recurrence relations?

▶ Substitution method
▶ Iteration method
▶ Recursion tree method
▶ Master method (D&C)
▶ Muster Theorem (S&C)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 21/87

 School of Computer Science and Engineering

Substitution method
- In Substitution method there are two steps :
1 - First guess the solution
2 - Second use mathematical induction to find the constants and
show that the solution works.
- This method is powerful, but depends on the correctness of the
guess.
- Method can be used for either upper or lower bounds on a
recurrence.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 22/87

 School of Computer Science and Engineering

Example of Substitution method

1. Prove that the solution of T (n) = 2T (n/2) + n is O(n lg n)
2. Find the solution of the recurrence relation
√
T (n) = 2T ( n) + lg n
3. Show that the solution of T (n) = 2T (n/2) + n is Ω(n lg n)
4. Show that the solution of T (n) = T (n/2) + 1 is O(lg n)
5. Find the solution of T (n) = T (n − 1) + n.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 23/87

 School of Computer Science and Engineering

Solution Example 1 of Substitution method

Example 1. Prove that the solution of T (n) = 2T (n/2) + n is
O(n lg n)
Solution:
Soln is already given so no need to guess the soln. We have to
prove that T (n) ≤ cn lg n for some constant c > 0 and for all
n > n0 .

T (n) = 2T (n/2) + n (1)

T (n) = O(n lg n) ⇒ T (n) ≤ cn lg n (2)

⇒ T (n) = O(n lg n) then it must be the solution for the input size
n/2.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 24/87

 School of Computer Science and Engineering

substitute the value of n as n/2 in Eq. 2.

T (n/2) ≤ c(n/2) lg(n/2) (3)

Substitute the value of T (n/2) from Eq. 3 into Eq. 1.

T (n) ≤ 2(c(n/2) lg(n/2)) + n

⇒ T (n) ≤ cn lg(n/2) + n
⇒ T (n) ≤ cn lg n − cn lg 2 + n
⇒ T (n) ≤ cn lg n − cn + n
⇒ T (n) ≤ cn lg n − n(c − 1)
⇒ T (n) ≤ cn lg n ∀c ≥ 1, n ≥ 2
∴ T (n) = O(n lg n)
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 25/87
 School of Computer Science and Engineering

Solution Example 2 of Substitution method

Example 2. Find the solution of the recurrence relation
√
T (n) = 2T ( n) + lg n
Solution:
Step 1 is to guess the solution but it is very hard to guess for the
given recurrence relation.
So First we have to simplify the relation by changing variables.

√
T (n) = 2T ( n) + lg n (given) (4)

Take:

lg n = m (5)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 26/87

 School of Computer Science and Engineering

⇒ n = 2m (6)

Put value of n from Eq. 6 into Eq. 4

T (2m ) = 2T (2m/2 ) + m (7)

Rename the recurrence relation Eq. 7 as S(m) = T (2m ) and

S(m/2) = T (2m/2 )

⇒ S(m) = 2S(m/2) + m (8)

Now we can guess the solution as

S(m) = O(m lg m) (9)

Put back the value of S(m) = T (2m ) and m from Eq. 5 into Eq. 9

T (n) = O(lg n lg lg n) (10)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 27/87

 School of Computer Science and Engineering

Solution Example 3 of Substitution method

Example 3. Show that the solution of T (n) = 2T (n/2) + n is
Ω(n lg n)
Solution:
We have to prove that T (n) ≥ cn lg n for some constant c > 0 and
for all n > n0 .

T (n) = 2T (n/2) + n (11)

T (n) = Ω(n lg n) ⇒ T (n) ≥ cn lg n (12)

⇒ T (n) = Ω(n lg n) then it must be the solution for the input size
n/2.
substitute the value of n as n/2 in Eq. 12.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 28/87

 School of Computer Science and Engineering

T (n/2) ≥ c(n/2) lg(n/2) (13)

Substitute the value of T (n/2) from Eq. 13 into Eq. 11.

T (n) ≥ 2(c(n/2) lg(n/2)) + n

⇒ T (n) ≥ cn lg(n/2) + n
⇒ T (n) ≥ cn lg n − cn lg 2 + n
⇒ T (n) ≥ cn lg n − cn + n
⇒ T (n) ≥ cn lg n + n(1 − c)
⇒ T (n) ≥ cn lg n ∀c ≤ 1, n ≥ 2
∴ T (n) = Ω(n lg n)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 29/87

 School of Computer Science and Engineering

Solution Example 4 of Substitution method

Example 4. Show that the solution of T (n) = T (n/2) + 1 is
O(lg n)
Solution:
We have to prove that T (n) ≤ c lg n for some constant c > 0 and
for all n > n0 .

T (n) = T (n/2) + 1 (14)

T (n) = O(lg n) ⇒ T (n) ≤ c lg n (15)

⇒ T (n) = O(lg n) then it must be the solution for the input size
n/2.
substitute the value of n as n/2 in Eq. 15.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 30/87

 School of Computer Science and Engineering

T (n/2) ≤ c lg(n/2) (16)

Substitute the value of T (n/2) from Eq. 16 into Eq. 14.

T (n) ≤ c lg(n/2)) + 1

⇒ T (n) ≤ c lg(n/2) + 1
⇒ T (n) ≤ c lg n − c lg 2 + 1
⇒ T (n) ≤ c lg n − c + 1
⇒ T (n) ≤ c lg n − (c − 1)
⇒ T (n) ≤ c lg n ∀c ≥ 1, n ≥ 2
∴ T (n) = O(lg n)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 31/87

 School of Computer Science and Engineering

Solution Example 5 of Substitution method

Example 5. Find the solution of T (n) = T (n − 1) + n.
Solution:
Guess the solution be O(n2 ). Now we have to prove that
T (n) ≤ cn2 for some constant c > 0 and for all n > n0 .

T (n) = T (n − 1) + n (17)

T (n) = O(n2 ) ⇒ T (n) ≤ cn2 (18)

⇒ T (n) = O(n2 ) then it must be the solution for the input size
n − 1.
substitute the value of n as n − 1 in Eq. 18.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 32/87

 School of Computer Science and Engineering

T (n − 1) ≤ c(n − 1)2 (19)

Substitute the value of T (n − 1) from Eq. 19 into Eq. 17.

T (n) ≤ c(n − 1)2 + n

⇒ T (n) ≤ c(n2 − 2n + 1) + n
⇒ T (n) ≤ cn2 − 2cn + c + n
⇒ T (n) ≤ cn2 − (2c − 1)n + c
Take value of c such that (2c − 1) ≥ c

⇒ T (n) ≤ cn2 ∀c ≥ 1, n ≥ 1

∴ T (n) = O(n2 )
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 33/87
 School of Computer Science and Engineering

Iteration method
- In iteration method, expend the right hand side of the recurrence
relation.
- Try to find out the series and number of terms in the series.
- Find out the sum of the series

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 34/87

 School of Computer Science and Engineering

Example of Iteration method

1. Find the solution of T (n) = 2T (n/2) + n
2. Find the solution of T (n) = 3T (n/4) + Θ(n2 )
3. Find the solution of T (n) = T (n − 1) + n4
√
4. Find the solution of T (n) = T ( n) + n

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 35/87

 School of Computer Science and Engineering

Example 1 for Iteration method

Example 1 - Find the solution of T (n) = 2T (n/2) + n
Take

T (n) = 2T (n/2) + n (20)

Find the value of T (n/2) = 2T (n/4) + n/2 from Eq. 20 and put
into Eq. 20

⇒ T (n) = 2(2T (n/4) + n/2) + n

T (n) = 4T (n/4) + 2n (21)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 36/87

 School of Computer Science and Engineering

Again find the value of T (n/4) = 2T (n/8) + n/4 from Eq. 20 and
put into Eq. 21

⇒ T (n) = 4(2T (n/8) + n/4) + 2n

T (n) = 8T (n/8) + 3n (22)

Repeating this for i times T (n) will be

⇒ T (n) = 2i T (n/2i ) + in (23)

T (n/2i ) will terminate when n/2i = 1 i.e T (1)

⇒ n/2i = 1

⇒ n = 2i
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 37/87
 School of Computer Science and Engineering

⇒ lg n = i
So after lg n iteration, the recurrence term will be terminated.
Eq. 23 will be

⇒ T (n) = 2lg n T (1) + n lg n

⇒ T (n) = nT (1) + n lg n
⇒ T (n) ≤ cn + n lg n, ∀c ≥ T (1)
⇒ T (n) ≤ cn lg n + n lg n, ∀n ≥ 2
⇒ T (n) = (c + 1)n lg n
⇒ T (n) ≤ c1 n lg n, ∀c1 ≥ (c + 1) > 0, ∀n ≥ 2
∴ T (n) = O(n lg n)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 38/87

 School of Computer Science and Engineering

Example 2 for Iteration method

Example 2 - Find the solution of T (n) = 3T (n/4) + Θ(n2 )
Take for c > 0

T (n) = 3T (n/4) + cn2 (24)

Find the value of T (n/4) = 3T (n/16) + c(n/4)2 from Eq. 24 and

put into Eq. 24

 
⇒ T (n) = 3 3T (n/16) + c(n/4)2 + cn2

3
 
T (n) = 9T (n/16) + 1 + cn2 (25)
16

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 39/87

 School of Computer Science and Engineering

Again find the value of T (n/16) = 3T (n/64) + c(n/16)2 from

Eq. 24 and put into Eq. 25
3
   
⇒ T (n) = 9 3T (n/64) + c(n/16)2 + 1 + cn2
16

2 !
3 3

T (n) = 27T (n/64) + 1 + + cn2 (26)
16 16

Repeating this for i times T (n) will be

2 (i−1) !
3 3 3
 
⇒ T (n) = 3i T (n/4i ) + 1 + + + ··· + cn2
16 16 16
(27)

T (n/4i ) will terminate when n/4i = 1 i.e T (1)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 40/87
 School of Computer Science and Engineering

⇒ n/4i = 1

⇒ n = 4i
⇒ log4 n = i
So after log4 n iteration, the recurrence term will be terminated.
Eq. 27 will be
2 (log4 n−1) !
3 3 3
 
log4 n
⇒ T (n) = 3 T (1) + 1 + + + ··· + cn2
16 16 16

2 (log4 n−1) !
3 3 3
 
log4 3
⇒ T (n) = n T (1) + 1 + + + ··· + cn2
16 16 16

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 41/87

 School of Computer Science and Engineering
2 !
3 3

⇒ T (n) ≤ c1 n + 1 + + + ... cn2 , ∀c1 ≥ T (1)
16 16

1
 
⇒ T (n) ≤ c1 n + cn2
1 − 3/16

16
 
⇒ T (n) ≤ c1 n + cn2
13

16
 
2
⇒ T (n) ≤ c1 n + cn2 , ∀n ≥ 1
13

13c1 + 16c
 
⇒ T (n) ≤ n2
13

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 42/87

 School of Computer Science and Engineering
13c1 + 16c
⇒ T (n) ≤ c2 n2 where ∀c2 ≥ > 0 and ∀n ≥ 1
13
∴ T (n) = O(n2 )

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 43/87

 School of Computer Science and Engineering

Example 3 for Iteration method

Example 3 - Find the solution of T (n) = T (n − 1) + n4

T (n) = T (n − 1) + n4 (28)

Find the value of T (n − 1) = T (n − 2) + (n − 1)4 from Eq. 28 and

put into Eq. 28

 
⇒ T (n) = T (n − 2) + (n − 1)4 + n4

T (n) = T (n − 2) + (n − 1)4 + n4 (29)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 44/87

 School of Computer Science and Engineering

Again find the value of T (n − 2) = T (n − 3) + (n − 2)4 from

Eq. 28 and put into Eq. 29
 
⇒ T (n) = T (n − 3) + (n − 2)4 + (n − 1)4 + n4

T (n) = T (n − 3) + (n − 2)4 + (n − 1)4 + n4 (30)

Repeating this for i times T (n) will be

⇒ T (n) = T (n − i) + (n − i + 1)4 + · · · + (n − 1)4 + n4 (31)

T (n − i) will terminate when n − i = 0 i.e T (0)

⇒n−i =0

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 45/87

 School of Computer Science and Engineering

⇒i =n
So after n iteration, the recurrence term will be terminated. Eq. 31
will be
⇒ T (n) = T (0) + 14 + 24 + 34 + · · · + (n − 1)4 + n4

⇒ T (n) ≤ T (0) + n4 + n4 + · · · + n4 , ∀n ≥ 1

⇒ T (n) ≤ T (0) + nn4

⇒ T (n) ≤ cn5 + n5 , ∀c ≥ T (0)

⇒ T (n) ≤ (c + 1)n5

⇒ T (n) ≤ c1 n5 where ∀c1 ≥ (c + 1) > 0 and ∀n ≥ 1

∴ T (n) = O(n5 )
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 46/87
 School of Computer Science and Engineering

Example 4 for Iteration method

√
Example 4 - Find the solution of T (n) = T ( n) + n

√
T (n) = T ( n) + n (32)
√ √ √
Find the value of T ( 2 n) = T ( 4 n) + 2 n from Eq. 32 and put into
Eq. 32

√ √

⇒ T (n) = T ( 4 n) + 2 n + n

√ √
T (n) = T ( 4 n) + 2 n + n (33)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 47/87

 School of Computer Science and Engineering
√ √ √
Again find the value of T ( 4 n) = T ( 8 n) + 4 n from Eq. 32 and
put into Eq. 33
√ √
√
⇒ T (n) = T ( 8 n) + 4 n + 2 n + n

√ √ √
T (n) = T ( 8 n) + 4 n + 2 n + n (34)

Repeating this for i times T (n) will be

√i √
i−1 √ √
⇒ T (n) = T ( 2 n) + 2 n + · · · + 4 n + 2 n + n (35)
√i √i
T ( 2 n) will terminate when 2 n = 2 i.e T (2)

√
2i
⇒ n=2

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 48/87

 School of Computer Science and Engineering
√
2i
⇒ lg( n) = lg 2
1
⇒ i lg n = 1
2
⇒ lg n = 2i
⇒ lg lg n = i
So after lg lg n iteration, the recurrence term will be terminated.
Eq. 35 will be
√ √ √
i−1
⇒ T (n) = n + 2 n + 4 n + · · · + 2 n + T (2)

⇒ T (n) ≤ n + n + n + . . . lg lg n times

⇒ T (n) ≤ n lg lg n

∴ T (n) = O(n lg lg n)
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 49/87
 School of Computer Science and Engineering

Recursion tree method

- Represent the problem as a tree taking non recurrence term on
the root
- Expend the leaf node by using the recurrence relation
- Stop the process when input size reaches at a particular level
- Each node represent the cost of a sub problem
- Sum of all nodes of a level is level-cost
- Sum of all level is the cost of the problem

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 50/87

 School of Computer Science and Engineering

Examples of Recursion tree method

1. Find the solution of T (n) = 2T (n/2) + n
2. Find the solution of T (n) = 3T (n/4) + cn2
3. Find the solution of T (n) = T (n/2) + 1
4. Find the upper and lower bound solution of
T (n) = T (n/3) + T (2n/3) + cn
5. Determine a good asymptotic upper bound on the recurrence
T (n) = 3T (n/2) + n.
6. Determine a good asymptotic upper bound on the recurrence
T (n) = T (n/2) + n2 .
7. Determine a good asymptotic upper bound on the recurrence
T (n) = T (n − 1) + T (n/2) + n.
8. Give an asymptotically tight solution to the recurrence
T (n) = T (n − a) + T (a) + cn, where a ≥ 1 and c > 0 are
constants.
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 51/87
 School of Computer Science and Engineering

Example 1 of Recursion tree method

1. Find the solution of T (n) = 2T (n/2) + n
n

T ( n2 ) T ( n2 )

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 52/87

 School of Computer Science and Engineering

n n
2 2

T ( 2n2 ) T ( 2n2 ) T ( 2n2 ) T ( 2n2 )

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 53/87

 School of Computer Science and Engineering

n n
2 2

n n n n
22 22 22 22

.. .. .. .. .. .. .. ..
. . . . . . . .

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 54/87

 School of Computer Science and Engineering

n n
2 2

n n n n
22 22 22 22

.. .. .. .. .. .. .. ..
. . . . . . . .

T ( 2ni ) · · · · · · · · · · · · · · T ( 2ni )

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 55/87

 School of Computer Science and Engineering

Example 2 of Recursion tree method

2. Find the solution of T (n) = 3T (n/4) + cn2
cn2

T ( n4 ) T ( n4 ) T ( n4 )
cn2

n 2 n 2 n 2




c 4 c 4 c 4

n n n n n n n n
T ( 16 ) T ( 16 ) T ( 16 ) T ( 16 ) T ( 16 ) T ( 16 ) T ( 16 ) T ( 16 ) T(
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 56/87
 School of Computer Science and Engineering

Example 2 of Recursion tree method

2. Find the solution of T (n) = 3T (n/4) + cn2
cn2

n 2 n 2 n



c 4 c 4 c 4

n 2 n 2 n 2 n 2 n 2 n 2 n 2 n








c 16 c 16 c 16 c 16 c 16 c 16 c 16 c 16

.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
. . . . . . . . . . . . . . . . . . . . . . .

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 57/87

 School of Computer Science and Engineering

Master method (D&C)

Master method is based on the Master Theorem, which states as:
Let a ≥ 1 and b > 1 be constants, let f (n) be an asymptotically
positive function, and let T (n) be defined on the non-negative
integers by the recurrence
n
T (n) = aT ( ) + f (n)
b
Then T (n) has the following asymptotic bounds:
1. if f (n) = O(nlogb a−ϵ ) for some constant ϵ > 0, then
T (n) = Θ(nlogb a ).
2. f (n) = Θ(nlogb a ), then T (n) = Θ(nlogb a lg n)
3. if f (n) = Ω(nlogb a+ϵ ) for some constant ϵ > 0, and if
af (n/b) ≤ cf (n) for some constant c < 1 and all sufficiently
large n, then T (n) = Θ(f (n)).
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 58/87
 School of Computer Science and Engineering

Examples of Master method (D&C)

n


1. Find the solution of T (n) = 9T +n
 3
2. Find the solution of T (n) = T 2n3 +1
3T n4 + n lg n


3. Find the solution of T (n) =
2T n2 + n lg n


4. Find the solution of T (n) =
2T n2 + lgnn


5. Find the solution of T (n) =
2T n2 + Θ(n)


6. Find the solution of T (n) =
8T n2 + Θ(n2 )


7. Find the solution of T (n) =
4T n2 + Θ(n3 )


8. Find the solution of T (n) =

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 59/87

 School of Computer Science and Engineering

Solution of Examples 1 of Master method (D&C)

n


1. Find the solution of T (n) = 9T 3 +n
n
+ n with T (n) = aT bn + f (n)



Comparing T (n) = 9T 3
a = 9 ≥ 1, b = 3 > 1 and f (n) = n so we can apply Master
Method to solve this recursion.
As nlogb a = nlog3 9 = 2
 n is polynomially greater then f (n) = n.
so n = O nlog3 9−ϵ where for any 0 < ϵ ≤ 1.
Case 1 of Master Method will be applied and solution will be

   
T (n) = Θ nlog3 9 = Θ n2

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 60/87

 School of Computer Science and Engineering

Solution of Examples 2 of Master method (D&C)

 
2n
2. Find the solution of T (n) = T 3 +1
 
2n n


Comparing T (n) = T 3 + n with T (n) = aT b + f (n)
a = 1 ≥ 1, b = 32 > 1 and f (n) = n0 = 1 so we can apply Master
Method to solve this recursion.
As
log 3 1
nlogb a = n 2 = n0 = 1
is polynomially
 equal
 to f (n) = 1.
log 3 1
so n0 = Θ n 2 = Θ(n0 ) = Θ(1).
Case 2 of Master Method will be applied and solution will be
 
log 3 1  
T (n) = Θ n 2 lg n = Θ n0 lg n = Θ(lg n)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 61/87

 School of Computer Science and Engineering

Solution of Examples 3 of Master method (D&C)

n


3. Find the solution of T (n) = 3T 4 + n lg n
n
+ n lg n with T (n) = aT bn + f (n)



Comparing T (n) = 3T 4
a = 3 ≥ 1, b = 4 > 1 and f (n) = n lg n so we can apply Master
Method to solve this recursion.
As nlogb a = nlog4 3 = n0.79 is polynomially less than f (n) = n lg n.
so n lg n = Ω(n(log4 3+ϵ) ) = n(0.79+ϵ) for ϵ = 0.2
Also
n n
 
3f (n/4) = 3 lg
4 4
3 n
 
⇒ n lg
4 4
3 3
⇒ n lg n − n lg 4
4 4
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 62/87
 School of Computer Science and Engineering
3 3
⇒ n lg n − n
4 2
3 3
⇒ n lg n − n ≤ cn lg n
4 2
where 34 ≤ c < 1.
Case 3 of Master Method will be applied and solution will be

T (n) = Θ (f (n)) = Θ (n lg n)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 63/87

 School of Computer Science and Engineering

Solution of Examples 4 of Master method (D&C)

n


4. Find the solution of T (n) = 2T 2 + n lg n
n
+ n lg n with T (n) = aT bn + f (n)



Comparing T (n) = 2T 2
a = 2 ≥ 1, b = 2 > 1 and f (n) = n lg n so we can apply Master
Method to solve this recursion.
As nlogb a = nlog2 2 = n1 is not polynomially less than, greater than
or equal to f (n) = n lg n. It is asymptotically less than n lg n. It
lies between the gaps of Case 2 and Case 3.
So it cann’t be solved using Master Method.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 64/87

 School of Computer Science and Engineering

Solution of Examples 5 of Master method (D&C)

n n


5. Find the solution of T (n) = 2T 2 + lg n
Comparing T (n) = 2T 2 + lgnn with T (n) = aT bn + f (n)
n

a = 2 ≥ 1, b = 2 > 1 and f (n) = lgnn so we can apply Master

Method to solve this recursion.
As nlogb a = nlog2 2 = n1 is not polynomially less than, greater than
or equal to f (n) = lgnn . It is asymptotically greater than lgnn . It lies
between the gaps of Case 1 and Case 2.
So it cann’t be solved using Master Method.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 65/87

 School of Computer Science and Engineering

Solution of Examples 6 of Master method (D&C)

n


6. Find the solution of T (n) = 2T 2 + Θ(n)
n
+ Θ(n) with T (n) = aT bn + f (n)



Comparing T (n) = 2T 2
a = 2 ≥ 1, b = 2 > 1 and f (n) = Θ(n) = cn so we can apply
Master Method to solve this recursion.
As

nlogb a = nlog2 2 = n1

is polynomially equal to f (n) = cn.

so cn = Θ (n).
Case 2 of Master Method will be applied and solution will be

 
T (n) = Θ n1 lg n = Θ (n lg n)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 66/87

 School of Computer Science and Engineering

Solution of Examples 7 of Master method (D&C)

n
+ Θ(n2 )


7. Find the solution of T (n) = 8T 2
Comparing T (n) = 8T 2 + Θ(n2 ) with T (n) = aT bn + f (n)
n

a = 8 ≥ 1, b = 2 > 1 and f (n) = Θ(n2 ) = cn2 so we can apply

Master Method to solve this recursion.
As

nlogb a = nlog2 8 = n3

is polynomially greater than f (n) = cn2 .

so cn2 = O(n3−ϵ ) for 0 < ϵ ≤ 1
Case 1 of Master Method will be applied and solution will be

 
T (n) = Θ n3

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 67/87

 School of Computer Science and Engineering

Solution of Examples 8 of Master method (D&C)

n
+ Θ(n3 )


8. Find the solution of T (n) = 4T 2
Comparing T (n) = 4T 2 + Θ(n3 ) with T (n) = aT bn + f (n)
n

a = 4 ≥ 1, b = 2 > 1 and f (n) = Θ(n3 ) = dn3 , d > 0 so we can

apply Master Method to solve this recursion.
As

nlog2 4 = n2

is polynomially less than f (n) = dn3 .

Also af ( bn ) ≤ cf (n) for 0 < c < 1
 3
n
⇒ 4d
2

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 68/87

 School of Computer Science and Engineering
4
⇒ dn3
8
1 3
⇒ dn ≤ cdn3
2
Where 12 ≤ c < 1, ⇒ c = 0.75
so dn3 = Ω(n2+ϵ ) for 0 < ϵ ≤ 1
Case 3 of Master Method will be applied and solution will be

 
T (n) = Θ n3

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 69/87

 School of Computer Science and Engineering

Muster Theorem (S&C)

Let a > 0 and b > 0 be constants, let f (n) be an asymptotically
positive function such that f (n) = O(nd ) for d ≥ 0 and let T (n)
be defined on the positive integers by the recurrence

T (n) = aT (n − b) + f (n)

Then T (n) has the following asymptotic bounds:

1. if a < 1 then T (n) = O(nd )
2. if a = 1 then T (n) = O(nd+1 )
n
3. if if a > 1 then T (n) = O(a b nd )

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 70/87

 School of Computer Science and Engineering

Proof:
Expend the left hand side term of given recurrence

T (n) = aT (n − b) + f (n)

⇒ T (n) = a2 T (n − 2b) + af (n − b) + f (n)

⇒ T (n) = a3 T (n − 3b) + a2 f (n − 2b) + af (n − b) + f (n)
⇒ T (n) = ai T (n − ib) + ai−1 f (n − (i − 1)b) + · · · + af (n − b) + f (n)
n
This will be terminated when n − ib = 0 that is i = b

n
   
n n
⇒ T (n) = a b T (0)+a b −1 f n− − 1 b +· · ·+af (n−b)+f (n)
b
n
b
−1
X n
⇒ T (n) = ai f (n − ib) + a b T (0)
i=0
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 71/87
 School of Computer Science and Engineering
n
Xb
⇒ T (n) ≤ ai f (n − ib)
i=0
 n 
b
X
⇒ T (n) = O nd ai 
i=0

Now there are 3 cases:

1. if a < 1 then

n
n
b
X
i1 − a b +1 1
a = ≤ = O(1)
i=0
1−a 1−a
 
⇒ T (n) = O nd O(1)
 
⇒ T (n) = O nd
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 72/87
 School of Computer Science and Engineering

2. if a = 1 then

n n
b b
X
i
X n
a = 1= + 1 = O(n)
i=0 i=0
b
 
⇒ T (n) = O nd O(n)
 
⇒ T (n) = O nd+1

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 73/87

 School of Computer Science and Engineering

3. if a > 1 then

n
n
b
X a b +1 − 1 n
ai = = O(a b )
i=0
a−1
n
 
⇒ T (n) = O nd O(a b )
n
 
⇒ T (n) = O nd a b
so

d
O(n ) a<1


T (n) = O(nd+1 ) a=1
O(a bn nd )


a>1

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 74/87

 School of Computer Science and Engineering

Examples of Muster Theorem (S&C)

1. Find the solution of T (n) = 12 T (n − 1) + n
2. Find the solution of T (n) = 78 T (n − 1) + n3
3. Find the solution of T (n) = T (n − 2) + n
4. Find the solution of T (n) = T (n − 2) + n lg n
n
5. Find the solution of T (n) = T (n − 2) + lg n
6. Find the solution of T (n) = 2T (n − 2) + n
7. Find the solution of T (n) = 3T (n − 1) + n2

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 75/87

 School of Computer Science and Engineering

Solutions of Examples of Muster Theorem (S&C)

1. Find the solution of T (n) = 12 T (n − 1) + n
Here a = 12 , b = 1, f (n) = O(n), d = 1,
Case 1 applies. So the solution is :
 
T (n) = O nd

T (n) = O (n)
2. Find the solution of T (n) = 78 T (n − 1) + n3
Here a = 78 , b = 1, f (n) = O(n3 ), d = 3,
Case 1 applies. So the solution is :
 
T (n) = O nd
 
T (n) = O n3
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 76/87
 School of Computer Science and Engineering

3. Find the solution of T (n) = T (n − 2) + n

Here a = 1, b = 2, f (n) = O(n), d = 1,
Case 2 applies. So the solution is :
 
T (n) = O nd+1
 
T (n) = O n2
4. Find the solution of T (n) = T (n − 2) + n lg n
Here f (n) = n lg n, function is not polynomial of n so method
cann’t be applied.
a = 1, b = 2, f (n) = O(n2 ), d = 2,
Case 2 applies. So the solution is :
 
T (n) = O nd+1
 
T (n) = O n3
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 77/87
 School of Computer Science and Engineering

5. Find the solution of T (n) = T (n − 2) + lgnn

Here f (n) = lgnn , function is not polynomial of n so method
cann’t be applied.
a = 1, b = 2, f (n) = O(n), d = 1,
Case 2 applies. So the solution is :
 
T (n) = O nd+1
 
T (n) = O n2
6. Find the solution of T (n) = 2T (n − 2) + n
Here a = 2, b = 2, f (n) = O(n), d = 1,
Case 3 applies. So the solution is :
n
 
T (n) = O nd a b

n
 
T (n) = O n1 2 2
Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 78/87
 School of Computer Science and Engineering

7. Find the solution of T (n) = 3T (n − 1) + n2

Here a = 3, b = 1, f (n) = O(n2 ), d = 2,
Case 3 applies. So the solution is :
n
 
T (n) = O nd a b
 
T (n) = O n2 3n

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 79/87

 School of Computer Science and Engineering

Complexity analysis
Analyzing an algorithm means predicting the resources that the
algorithm requires. Resources may be memory, communication
bandwidth, computer hardware or CPU time. Our primary concern
is to measures the computational time required for the algorithm.
Running time:-The running time of an algorithm is the number of
primitive operations or steps executed on a particular input.
Why do we normally concentrate on finding only the worst-case
running time?
1. The worst-case running time of an algorithm gives us an
upper bound on the running time for any input. So it
guarantees that the algorithm will never slower than this.
2. In real applications, worst case normally occurs for example
searching a non existing data.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 80/87

 School of Computer Science and Engineering

3. Best case is like an ideal case which guarantees that the

algorithm will never faster than stated. Based upon this we
can’t allocate the resources.
4. Average case normally perform as worst case because normally
we take average case as average of best and worst or best for
half size input and worst for other half size.

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 81/87

 School of Computer Science and Engineering

Complexity analysis: Insertion sort

Insertion-Sort(A,N) Cost Times
1. for j = 2 to N c1 n
2. key = A[j] c2 n-1
Insert A[j] in sorted A[1] to A[j − 1]
3. i = j − 1 c3 n-1
Pn
4. while i > 0 and A[i] > key c4 tj
Pj=2
n
5. A[i + 1] = A[i] c5 (t j −1)
Pj=2
n
6. i = i − 1 c6 j=2 (tj −1)
while-end
7. A[i + 1] = key c7 n-1
for-end

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 82/87

 School of Computer Science and Engineering
n
X n
X
T (n) = c1 n + c2 (n − 1) + c3 (n − 1) + c4 tj + c5 (tj − 1)
j=2 j=2
n
X
+c6 (tj − 1) + c7 (n − 1)
j=2

n
X n
X n
X
⇒ T (n) = an + b + c4 tj + c5 (tj − 1) + c6 (tj − 1)
j=2 j=2 j=2

Now consider different cases:

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 83/87

 School of Computer Science and Engineering

1. Best Case: The algorithm performs best if key ≤ A[i] for

every value of j in step 4.
Then it executes only once for each value of j and total of n-1
times.
Step 5 and 6 will not be execute at all.
This is the case when array is already sorted

T (n) = an + b = O(n)

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 84/87

 School of Computer Science and Engineering

2. Worst Case: The algorithm performs worst if key > A[i] for
each value of j and stops only when i < 1 in step 4.
Then it will execute always j times for each value of
j = 2, 3, . . . , n
so
n
X (n − 1)(2 + n)
j=
j=2
2

and step 5 and 6 will execute

n
X (n − 1)n
(j − 1) =
j=2
2

This is the case when array is already sorted in reverse order

T (n) = an2 + bn + c = O(n2 )

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 85/87
 School of Computer Science and Engineering

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 86/87

 School of Computer Science and Engineering

Thank you
Please send your feedback or any queries to
ashokyadav@[Link]

Module-I: Introduction Dr. A K Yadav Design and Analysis of Algorithm 87/87