Design and analysis of Algorithms
Chapter-3
Mathematical analysis of
Algorithms
Revision on the analysis of Algorithms
• The analysis framework
Time Complexity
Space Complexity
• Measuring input size
mostly straight forward
e.g the maximum number in an array ,
number of elements in an array.
• Choose of parameters sometimes matter.
e.g nxn matrix
n->order of matrix
N-> total number of elements in the matrix
• Units of measuring Running Time
its a metrics that does not depend on some extraneous factors.
Through counting basic operations
(the operation that takes max time).
Non-recursive Algorithms
A non-recursive algorithm does the operations all at once, without calling itself.
E.g Bubble sort.
Time efficiency of nonrecursive
algorithms
General Plan for Analysis
Decide on parameter n indicating input size
Identify algorithm’s basic operation
Determine worst, average, and best cases for input of size n
Set up a sum for the number of times the basic operation is executed
Simplify the sum using standard formulas and rules.
Example 1: The Largest Element
T(n) = 1in-1 (1) = n-1 = (n) comparisons
Example 2: Element uniqueness problem
1 u l 1
i l
n 2
n 1 i (n 1) (n 2) ..... 1
i 0
T(n) = 0in-2 (i+1jn-1 (1))
= 0in-2 (n-i+1) = (n 1)n 1 2
= ( 2 ) comparisons
n (n 2 )
n 2 2
Example 3: Matrix multiplication
n 1 n 1 n 1
T(n) = 1
i 0 j 0 k 0
3
= ( n ) multiplications
Ignored addition for simplicity
Example 4: Counting binary digits
It cannot be investigated the way the previous examples are.
i
The halving game: Find integer i such that n/2 ≤ 1.
Answer: i ≤ log n. So, T(n) = (log n) divisions.
Another solution: Using recurrence relations.
Plan for Analysis of Recursive Algorithms
Decide on a parameter indicating an input’s size.
Identify the algorithm’s basic operation.
Check whether the number of times the basic op. is executed may vary
on different inputs of the same size. (If it may, the worst, average, and
best cases must be investigated separately.)
Set up a recurrence relation with an appropriate initial condition
expressing the number of times the basic op. is executed.
Solve the recurrence (or, at the very least, establish its solution’s order
of growth) by backward substitutions or another method.
Example 1 : Factorial: Recursive Algorithm
The stopping condition is n=0
A repetitive algorithm uses recursion whenever the algorithm appears
within the definition itself.
10
Example 1: Recursive evaluation of n!
Definition: n ! = 1 2 … (n-1) n for n ≥ 1 and 0! = 1
Recursive definition of n!: F(n) = F(n-1) n for n ≥ 1 and
F(0) = 1
Size:
n
Basic operation:
multiplication
Recurrence relation:
M(n) = M(n-1) (for F(n-1) ) + 1 (for the n
* F(n-1))
M(0) = 0
Solving the recurrence for M(n)
M(n) = M(n-1) + 1, M(0) = 0 (no multiplication when n=0)
M(n) = M(n-1) + 1
= (M(n-2) + 1) + 1 = M(n-2) + 2
= (M(n-3) + 1) + 2 = M(n-3) + 3
…
= M(n-i) + i
= M(0) + n
=n
The method is called backward substitution.
Example 2: The Tower of Hanoi
Puzzle
Towers of Hanoi (aka Tower of Hanoi) is a mathematical puzzle
invented by a French Mathematician Edouard Lucas in 1983.
•Initially the game has few discs arranged in the increasing order
of size in one of the tower.
• The number of discs can vary, but there are only three towers.
•The goal is to transfer the discs from one tower another tower.
However you can move only one disk at a time and you can
never place a bigger disc over a smaller disk. It is also understood
that you can only take the top most disc from any given tower.
13
Example 2: The Tower of Hanoi Puzzle
Recurrence for number of moves:
M(n) = 2M(n-1) + 1
0 Move Sequence for d = 3
7
The Tower of Hanoi Puzzle
Here's how to find the number of moves needed to transfer
larger numbers of disks from post A to post C, when M = the
number of moves needed to transfer n-1 disks from post A to
post C:
for 1 disk it takes 1 move to transfer 1 disk from post A to post
C;
for 2 disks, it will take 3 moves: 2M + 1 = 2(1) + 1 = 3
for 3 disks, it will take 7 moves: 2M + 1 = 2(3) + 1 = 7
for 4 disks, it will take 15 moves: 2M + 1 = 2(7) + 1 = 15
for 5 disks, it will take 31 moves: 2M + 1 = 2(15) + 1 = 31
for 6 disks... ?
Explicit Pattern
Number of Disks Number of Moves
1 1
2 3
3 7
4 15
5 31
6 63
Powers of two help reveal the pattern:
Number of Disks (n) Number of Moves
1 21 - 1 = 2 - 1 = 1
2 22 - 1 = 4 - 1 = 3 3 23
-1=8-1 =7
4 24 - 1 = 16 - 1 = 15
5 25 - 1 = 32 - 1 = 31
6 26 - 1 = 64 - 1 = 63
Fascinating fact
So the formula for finding the number of steps it takes to transfer
n disks from post A to post C is:
2 n- 1
Solving recurrence for number of
moves
M(n) = 2M(n-1) + 1, M(1) = 1
M(n) = 2M(n-1) + 1
= 2(2M(n-2) + 1) + 1 = 2^2*M(n-2) + 2^1 + 2^0
= 2^2*(2M(n-3) + 1) + 2^1 + 2^0
= 2^3*M(n-3) + 2^2 + 2^1 + 2^0
=…
= 2^(n-1)*M(1) + 2^(n-2) + … + 2^1 + 2^0
= 2^(n-1) + 2^(n-2) + … + 2^1 + 2^0
= 2^n -1
Mathimatical analysis of Recursive
algorithms
[Link] method
The most general method:
1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.
Substitution method
The most general method:
1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.
EXAMPLE: T(n) = 4T(n/2) + n
• [Assume that T(1) = (1).]
• Guess O(n3) . (Prove O and
separately.)
• Assume that T(k) ck3 for k < n .
• Prove T(n) cn3 by induction.
Example of substitution
T (n) 4T (n / 2) n
4c(n / 2)3 n
(c / 2)n3 n
cn3 ((c / 2)n3 n) desired – residual
cn3 desired
whenever (c/2)n3 – n 0, for
example, if c 2 and n 1.
residual
Example (continued)
• We must also handle the initial conditions,
that is, ground the induction with base
cases.
• Base: T(n) = (1) for all n < n0, where n0
is a suitable constant.
• For 1 n < n0, we have “(1)” cn3, if
we pick c big enough.
Example (continued)
• We must also handle the initial conditions,
that is, ground the induction with base
cases.
• Base: T(n) = (1) for all n < n0, where n0
is a suitable constant.
• For 1 n < n0, we have “(1)” cn3, if
we pick c big enough.
This bound is not tight!
A tighter upper bound?
We shall prove that T(n) = O(n2).
A tighter upper bound?
We shall prove that T(n) = O(n2).
Assume that T(k) ck2 for k <
n: T (n) 4T (n / 2) n
4c(n / 2)2 n
cn2 n
O(n2 )
A tighter upper bound?
We shall prove that T(n) = O(n2).
Assume that T(k) ck2 for k
< n: T (n) 4T (n / 2) n
4c(n / 2)2 n
cn2 n
O(n 2 ) Wrong!
We must prove the I.H.
A tighter upper bound?
We shall prove that T(n) = O(n2).
Assume that T(k) ck2 for k
< n: T (n) 4T (n / 2) n
4c(n / 2)2 n
cn2 n
cnO(n
2 2(n) [ desired – residual ]
) Wrong!
We
cn 2must for prove
no choice of
the I.H.c > [Link]!
A tighter upper bound!
IDEA: Strengthen the inductive hypothesis.
• Subtract a low-order term.
Inductive hypothesis: T(k) c1k2 – c2k for k < n.
A tighter upper bound!
IDEA: Strengthen the inductive hypothesis.
• Subtract a low-order term.
Inductive hypothesis: T(k) c1k2 – c2k for k < n.
T(n) = 4T(n/2) + n
= 4(c1(n/2)2 – c2(n/2)) + n
= c1n2 – 2c2n + n
= c1n2 – c2n – (c2n – n)
c1n2 – c2n if c2 1.
A tighter upper bound!
IDEA: Strengthen the inductive hypothesis.
• Subtract a low-order term.
Inductive hypothesis: T(k) c1k2 – c2k for k < n.
T(n) = 4T(n/2) + n
= 4(c1(n/2)2 – c2(n/2)) + n
= c1n2 – 2c2n + n
= c1n2 – c2n – (c2n – n)
c1n2 – c2n if c2 1.
Pick c1 big enough to handle the initial conditions.
II. Recursion-tree method
• A recursion tree models the costs (time) of a
recursive execution of an algorithm.
• The recursion-tree method can be unreliable,
just like any method that uses ellipses (…).
• The recursion-tree method promotes intuition,
however.
• The recursion tree method is good for
generating guesses for the substitution method.
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
T(n)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
T(n/4) T(n/2)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2
T(n/16) T(n/8) T(n/8) T(n/4)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
…
(1)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
(n/4)2 (n/2)2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
…
(1)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2
…
(1)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 n 2
256
…
…
(1)
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2 n2
(n/4)2 (n/2)2 5 n2
16
(n/16)2 (n/8)2 (n/8)2(n/4)2 25 n 2
256
…
…
(1) 2
5
1 16
5
16 16
25 3
Total = n
= (n2) geometric series
L
III. The master method
The master method applies to recurrences of
the form
T(n) = a T(n/b) + f (n) ,
where a 1, b > 1, and f is
asymptotically positive.
Three common cases
Compare f (n) with nlogba:
1. f (n) = O(nlogba – ) for some constant > 0.
• f (n) grows polynomially slower than nlogba
(by an n factor).
Solution: T(n) =
(nlogba) .
Three common cases
Compare f (n) with nlogba:
1. f (n) = O(nlogba – ) for some constant > 0.
• f (n) grows polynomially slower than nlogba
(by an n factor).
Solution: T(n) =
(nlogba) .
2. f (n) = (nlogba lgkn)
for some constant k
0.
log a
Three common cases (cont.)
Compare f (n) with nlogba:
3. f (n) = (nlogba + ) for some constant > 0.
• f (n) grows polynomially faster than nlogba (by
an n factor),
and f (n) satisfies the regularity condition that
af (n/b) cf (n) for some constant c < 1.
Solution: T(n) = ( f (n)) .
Examples
EX. T(n) = 4T(n/2) + n
a = 4, b = 2 nlogba = n2; f (n) = n.
CASE 1: f (n) = O(n2 – ) for = 1.
T(n) = (n2).
Examples
EX. T(n) = 4T(n/2) + n
a = 4, b = 2 nlogba = n2; f (n) = n.
CASE 1: f (n) = O(n2 – ) for = 1.
T(n) = (n2).
EX. T(n) = 4T(n/2) + n2
a = 4, b = 2 nlogba = n2; f (n) = n2.
CASE 2: f (n) = (n2lg0n), that is, k = 0.
T(n) = (n2lg n).
Examples
EX. T(n) = 4T(n/2) + n3
a = 4, b = 2 nlogba = n2; f (n) = n3.
CASE 3: f (n) = (n2 + ) for = 1
and 4(n/2)3 cn3 (reg. cond.) for c = 1/2.
T(n) = (n3).
Examples
EX. T(n) = 4T(n/2) + n3
a = 4, b = 2 nlogba = n2; f (n) = n3.
CASE 3: f (n) = (n2 + ) for = 1
and 4(n/2)3 cn3 (reg. cond.) for c = 1/2.
T(n) = (n3).
EX. T(n) = 4T(n/2) + n2/lg n
a = 4, b = 2 nlogba = n2; f (n) = n2/lg n.
Master method does not [Link] particular,
for every constant > 0, we have n (lg
n).
Idea of master theorem
Recursion tree:
f a
(n) …
f f f
(n/b) (n/b) (n/b)
a
f (n/b2) f (n/b2) … f (n/b2)
…
(1)
Idea of master theorem
Recursion tree:
f f
a
(n) … (n)
f f (n/b) f (n/b) af
(n/b) a (n/b)
a2 f (n/b2)
f (n/b2) f (n/b2) … f (n/b2)
…
…
(1)
Idea of master theorem
Recursion tree:
f f
a
(n) … (n)
f f (n/b) f (n/b) af
h = logbn (n/b) a (n/b)
a2 f (n/b2)
f (n/b2) f (n/b2) … f (n/b2)
…
…
(1)
Idea of master theorem
Recursion tree:
f f
a
(n) … (n)
f f (n/b) f (n/b) af
h = logbn (n/b) a (n/b)
a2 f (n/b2)
f (n/b2) f (n/b2) … f (n/b2)
#leaves = ah
…
…
= alogbn
nlogba (1)
(1) = nlogba
Idea of master theorem
Recursion tree:
f f
a
(n) … (n)
f f (n/b) f (n/b) af
h = logbn (n/b) a (n/b)
a2 f (n/b2)
f (n/b2) f (n/b2) … f (n/b2)
…
…
nlogba (1)
(1)
(nlogba)
Idea of master theorem
Recursion tree:
f f
a
(n) … (n)
f f (n/b) f (n/b) af
h = logbn (n/b) a (n/b)
a2 f (n/b2)
f (n/b2) f (n/b2) … f (n/b2)
…
…
nlogba (1)
(1)
(nlogbalg n)
Idea of master theorem
Recursion tree:
f f
a
(n) … (n)
f f (n/b) f (n/b) af
h = logbn (n/b) a (n/b)
a2 f (n/b2)
f (n/b2) f (n/b2) … f (n/b2)
…
…
nlogba (1)
(1)
( f
(n))
Appendix: geometric series
n1
1 x x2 L x n 1 x for x
1x 1
1 x x L 1 x for |x| < 1
2 1
Return to last
slide
viewed.