Lecture # 21 - New

Design and Analysis of Algorithm
Tanveer Ahmed Siddiqui
Department of Computer Science

COMSATS University, Islamabad
Recap
Lecture No 7
Department of Computer Science 2

Mathematical Analysis of Iterative Algorithms
Steps in mathematical analysis of non recursive

algorithms
 Decide on parameter n indicating input size

 Identify algorithm’s basic operation
 Determine worst, average, and best case for input of
size n
 Set up summation for C(n) reflecting algorithm’s loop
structure
 Simplify summation using standard formulas
 Determine Orders of growth of C(n)

Food for thought
 Which algorithm is best?

Analysis of Algorithm
Lecture No 8
Analysis of Recursive Algorithm
(Analysis Framework.)

Learning Outcomes
After completing this lecture you will be able to

understand
 What is Recurrence Relation?
 How to derive Recurrence Relation from a
recursive algorithm.
 To convert an iterative algorithm into
recursive algorithm.
 How to compute Time complexity of recursive
algorithm.
 To compare iterative version with recursive
version.
What is Recurrence Relation?
 A recurrence relation is an equation which is

defined in terms of itself.
 It expresses the value of a function for an
argument n in terms of the values of function
for arguments less than n.
 Examples:

RecursiveRecursion
Method
Recursion (Size of Problem: n)

if( Stopping Criteria) // Base Case
return X
else
// General Case: decomposition strategy e.g., n-1, n/2 etc.
return Recursion (decomposition strategy)

 How to derive a recurrence relation

representing time complexity of a recursive
algorithm?
 Let T(n) denotes the time complexity of a
recursive algorithm A then,
 T(n) = Time complexity of base case + Time
complexity of each subproblem+ cost of other
work.
 Let there n0 be size of base case and suppose
ther are a subproblems each of size m1, m2,
m3….mk, and c be the cost of other work, then
 T(n) = T(n0) + T(m1) + T(m2) +…. T(mk) + c
 T(n) = T(n0) + T(m1) + T(m2) +…. T(mk) + c

 Suppose the time complexity of base case is d,
then
 T(n) = d+ T(m1) + T(m2) +…. T(mk) + c
 If each subproblem has equal size, then
 m1 = m2=m3 =……. mk= m
 T(n) = d+ aT(m) + c

Example-1:
Brute Force Example
 Set up and solve a recurrence relation for the
number of times the algorithm’s basic operation
is executed.
T(n)
T(n/2)
T(1) = d
T(n) = T(n/2) + c

Example-2: Computing
Brute Force Example a n

is executed.
T(n)
T(n-1)

Example-2:
Brute Maximum Number
Force Example
is executed.
 Solution:
T(n)
T(n-1)

Example-3:
Brute Maximum Number
Force Example
is executed.
 Solution: T(n)
T(n/2)
T(n/2)

Example-4: Binary Search

is executed.
T(n)
T(n/2)
T(n/2)

Example-5: Sum of n integers

Example-6: Merge Sort
Merge(A, p, q, r)
MergeSort (A, p, r) // sort A[p..r] by divide &
1 n1  q – p + 1
conquer
2 n2  r – q
1 if p < r
3 for i  1 to n1
2 then q  (p+r)/2
4 do L[i]  A[p + i – 1]
3 MergeSort (A, p, q) 5 for j  1 to n2
4 MergeSort (A, q+1, r) 6 do R[j]  A[q + j]
5 Merge (A, p, q, r) // merges A[p..q] with7 L[n1+1]  
A[q+1..r] 8 R[n2+1]  
9 i1
10 j1
11 for k p to r
12 do if L[i]  R[j]
13 then A[k]  L[i]
14 ii+1
15 else A[k]  R[j]
16 jj+1

Common Recurrence Types in Algorithm Analysis
 Decrease-by-One:
 T (n) = T (n − 1) + f (n)
 Decrease-by-a-Constant-Factor:
 T (n) = T (n/b) + f (n),
 Divide-and-Conquer
 T (n) = aT (n/b) + f (n)

SOLVING
RECURRENCE
RELATION
Solving Recurrence Relation
 There are four methods for solving a

recurrence relation
 Iteration Method(a.k.a Backward substitution)
 Recursion Tree
 The Master Theorem
 Substitution method for recurrence relations

Iteration
Method

The Iteration Method
 Convert the recurrence into a summation and try

to bound it using known series
 Iterate the recurrence until the initial condition
is reached.
 Use back-substitution to express the
recurrence in terms of n and the initial
(boundary) condition.

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

Example -1
T(n) = T(n-1) + 1
T(n-1) = T(n-2) + 1
T(n-2) = T(n-3) + 1
…
T(2) = T(1 ) + 1
T(n) = T(n-1) + c
T(n) = T(n-2) + c + c = T(n-2) + 2c
T(n) = T(n-3) + c+ c + c = T(n-3) + 3c

…………………………………
After ith substitution
T(n) = T(n-i ) + ic
Suppose after ith substitution, we reached at base case
n-i = 1 T(n) = T(1 ) + c(n-1)
i = n-1 T(n) = d+ c(n-1) = Θ(n)
Solving Recurrence Relations
T (n) = T (n − 1) + f (n)

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

Example-2
T(n) = T(n/2) +c
T(n/2) = T(n/4) +c
T(n) = T(n/2) + c T(n/4) = T(n/8) +c
= T(n/4)+ c + c = T(n/22)+ 2c
= T(n/8) +c + c + c = T(n/23)+ 3c
T(n) = T(n/2i)+ ic
Suppose after ith substitution, we reached at base case,
therefore
n = 2i i = log2n
T(n) =T(1) +d log2n = Θ(log2n)

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

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

Example-3
T(n) = 2T(n/2) + n T(n/2) = n/2 + 2T(n/4)

T(n) = 2T(n/2) +n
= 2(2T(n/4)+n/2) +n
= 4T(n/4)+ n + n = 22T(n/22)+ 2n
= 4(2T(n/8) + n/4)+ n + n
= 8T(n/8)+ n + n + n
T(n) = 2iT(n/2i) + in
Suppose after ith substitution, we reached at base case,
therefore n = 2i
= 2kT(1) +in = nT(1) + nlogn = = Θ(nlogn)
T (n) = aT (n/b) + f (n)

Recursion
Tree
Method

Recursion Tree Method
 Step 1: Assign (non-recursive) contribution of

a node (sub-problem) in each level
 Step 2: Compute total (non-recursive)
contribution across each level
 Step 3: Usually complete by evaluating a
summation – Go directly for  bound, not
separate  and .

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

T (n) = T (n − 1) + f (n)
 Expanding the recurrence into a tree
 The root of the recursion tree is a box (node) containing the
value f (n),
 the root has only one child, which is the root of (recursively
defined) recursion tree for the function T (n-1).
 The recursion stops when we get to the base case(s) of the
recurrence.
 Summing the cost at each level
 T (n) is just the sum of all values stored in the recursion tree.
For each i, the ith level of the tree contain 1 node, each with
value f(n-i), Thus,
where L is the depth of the recursion tree

 In this case recursion tree gives a look of a linked list because there is no left
Department of Computer
(right) child ofScience
any node .
Example
T (n) = T (n − 1) + n

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

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

value f (n),
 For each i, the ith level of the tree contain 1 node, each with
value f(n/bi)
recurrence.
 T (n) is just the sum of all values stored in the recursion tree

Example
T (n) = T (n/2) + n
T(n) = n/ 20 +n/ 21 + n/ 22 +n/ 23+ ………. n/ 2logn

= n(1 + ½ + ¼ + …………..1/n)
The sum of Geometric series can be 1found by using following formula
1 + ½ + ¼ + …………..1/n = 1  1 / 2
a1
=2 S
T(n) = 2n
1 r
T (n) = aT (n/b) + f (n)

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

value f (n),
 the root has a children, each of which is the root of
(recursively defined) recursion tree for the function T (n/b).
recurrence.

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

 T(n) is just the sum of all values stored in the recursion tree.
 For each i, the ith level of the tree contains ai nodes, each with
value f(n/bi), Thus

 We easily see that L = logbn, because n/bL = 1

Depth of complete binary tree
 We easily see that L = logbn, because n/bL = 1

 The depth d of full binary tree with n total nodes is:
d = log2 (n + 1) – 1
20+ 21+ 22 + ……… + 2d = d j=0 2j = 2d+1 – 1

Depth of complete binary tree
20+ 21+ 22 + ……… + 2d = d j=0 2j = 2d+1 – 1

Total number of nodes = 2d+1 – 1 = n
To find the value of d, we solve the above equation as under
2d+1 – 1 = n
2d+1 = n + 1
d + 1 = log2 (n + 1)
 d = log2 (n + 1) – 1
Recursion Tree Method: UP-SHOT

 In a recursion tree, each node represents the cost
of a single sub-problem somewhere in the set
of recursive function invocations.
 We sum the costs within each level of the tree to
obtain a set of per-level costs, and then we sum
all the per-level costs to determine the total cost
of all levels of the recursion.
Sn 

a1 r n  1  S
a1
r 1 1 r

Example
1
T(n) = T(n/2) + T(n/4) + n2

Example
1
T(n) = T(n/2) + T(n/4) + n2

Example
1
W(n) = 2W(n/2) + n2
 Subproblem size at level i is: n/2i

 Subproblem size hits 1 when 1 = n/2i  i = lgn
 Cost of the problem at level i = (n/2i)2 No. of nodes at level i = 2i
 Total cost: lg n 1 2
n lg n 1
 1 
i 
 1 
i
1
W ( n)  2
lg n
i 0
2
i
 2 W (1)  n
2
  2 
i 0
2
nn   2 
i 0
 O(n) n
1 1
 O ( n)  2n 2
2
 W(n) = O(n2)
Example
2

Your
Turn
T(n) = 3T(n/4) + cn2
• Subproblem size at level i is: n/4i

• Subproblem size hits 1 when 1 = n/4i  i = log4n
• Cost of a node at level i = c(n/4i)2
• Number of nodes at level i = 3i  last level has 3log4n = nlog43 nodes
• Total cost:
log4 n 1 i i
     

3 2 3 1
T (n)     cn   n log4 3
    cn 2   n log4 3  cn 2   n log4 3  O(n 2 )
i  0  16  i  0  16 
3
1
 T(n) =ofO(n
Department 2
) Science
Computer 50 16
Master
Theorem

Master Theorem
 T(n) = aT(n/b)+f(n), a ≥ 1, b > 1 What if a = 1?
Have we seen it?
 Master Theorem:
If f(n) є Θ(nd) where d ≥ 0 then
Θ(nd) if a < bd
T(n) є Θ(ndlogn) if a = bd Without going through
back-subs. we got it,
but not quite…
For adding n numbers with divide and conquer technique, the

number of additions A(n) is:
T(n) = 2T(n/2)+1
Here, a = ?, b = ?, d = ? a = 2, b = 2, d = 0
Which of the 3 cases holds ?a = 2 > bd = 20, case 3
T(n) = aT(n/b)+f(n), a ≥ 1, b > 1
If f(n) є Θ(nd) where d ≥ 0, then
Θ(nd) if a < bd
T(n) є Θ(ndlogn) if a = bd
T(n) = 2T(n/2)+6n-1?
T(n) = 3 T(n/2) + n a = 3, b = 2, f(n) є Θ(n1), so d = 1
a=3 > bd=21
T(n) = 3 T(n/2) + n2 a = 3, b = 2, f(n) є Θ(n2), so d = 2

a=3 < bd=22
T(n) = 4 T(n/2) + n2 a = 4, b = 2, f(n) є Θ(n2), so d = 2

a=4 = bd=22
T(n) = 0.5 T(n/2) + 1/n Master thm doesn’t apply,a<1, d<0
T(n) = 2 T(n/2) + n/lgn Master thm doesn’t apply f(n) not polynomial
T(n) = 64 T(n/8) – n2lgn f(n) is not positive, doesn’t apply

T(n) = 2n T(n/8) + n a is not constant, doesn’t apply
Substitution
Method

Substitution Method
1. Guess a solution
2. Use induction to prove that the solution

works

Substitution Method
 Guess a solution
 T(n) = O(g(n))
 Induction goal: apply the definition of the asymptotic notation
 T(n) ≤ cg(n), for some c > 0 and n ≥ n0

(strong induction)
 Induction hypothesis: T(k) ≤ c g(k) for all k < n
 Prove the induction goal

 Use the induction hypothesis to find some values of the
constants c and n0 for which the induction goal holds

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

Example
T(n) = T(n-1) + n
 Guess: T(n) = O(n2)
 Induction goal: T(n) ≤ c n2, for some c and n ≥ n0
 Induction hypothesis: T(n-1) ≤ c(n-1)2 for all k < n
 Proof of induction goal:
T(n) = T(n-1) + n ≤ c (n-1)2 + n
= cn2 – (2cn – c - n) ≤ cn2
if: 2cn – c – n ≥ 0  c ≥ n/(2n-1)  c ≥ 1/(2 –
1/n)
 For n ≥ 1  2 – 1/n ≥ 1  any c ≥ 1 will work
T (n) = T (n/b) + f (n)

Example
T(n) = T(n/2) + c
 Guess: T(n) = O(lgn)
 Induction goal: T(n) ≤ d lgn, for some d and n ≥ n0
 Induction hypothesis: T(n/2) ≤ d lg(n/2)
T(n) = T(n/2) + c ≤ d lg(n/2) + c
= d lgn – d + c ≤ d lgn
if: – d + c ≤ 0, d ≥ c
T (n) = aT (n/b) + f (n)

Example
T(n) = 2T(n/2) + n
 Guess: T(n) = O(nlgn)
 Induction goal: T(n) ≤ cn lgn, for some c and n ≥ n0
 Induction hypothesis: T(n/2) ≤ cn/2 lg(n/2)
T(n) = 2T(n/2) + n ≤ 2c (n/2)lg(n/2) + n
= cn lgn – cn + n ≤ cn lgn
if: - cn + n ≤ 0  c ≥ 1
Brute ForceWhich one is better?
Example
 Algorithms that find maximum in an array
Recursive 2
A[0..n-1]
 Solution:
Iterative
Recursive 1

Conclusion

Deriving Recurrence Relations
 How to derive a recurrence relation?
T(1) = d
T(n) = T(n/2) + c
General Recurrence Relation of Divide and Conq.

Important Recurrence Types

Lecture # 21 - New

Uploaded by

Copyright:

Available Formats

Lecture # 21 - New

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture # 21 - New

Uploaded by

Copyright:

Available Formats

Design and Analysis of Algorithm

Tanveer Ahmed Siddiqui

Department of Computer Science

Department of Computer Science 2

Steps in mathematical analysis of non recursive

 Decide on parameter n indicating input size

Department of Computer Science 3

 Which algorithm is best?

Department of Computer Science

Analysis of Recursive Algorithm

Department of Computer Science

After completing this lecture you will be able to

 A recurrence relation is an equation which is

Department of Computer Science

Recursion (Size of Problem: n)

Department of Computer Science

 How to derive a recurrence relation

 T(n) = T(n0) + T(m1) + T(m2) +…. T(mk) + c

Department of Computer Science

Department of Computer Science 11

 Set up and solve a recurrence relation for the

Department of Computer Science 12

Department of Computer Science 13

Department of Computer Science 14

 Set up and solve a recurrence relation for the

Department of Computer Science

Department of Computer Science

Department of Computer Science

Department of Computer Science

 There are four methods for solving a

Department of Computer Science

Department of Computer Science

 Convert the recurrence into a summation and try

Department of Computer Science 22

Department of Computer Science

T(n) = T(n-3) + c+ c + c = T(n-3) + 3c

Department of Computer Science

Department of Computer Science

Department of Computer Science 27

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

Department of Computer Science

Department of Computer Science

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

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

Department of Computer Science

Department of Computer Science

 Step 1: Assign (non-recursive) contribution of

Department of Computer Science 33

Department of Computer Science

where L is the depth of the recursion tree

Department of Computer Science

Department of Computer Science

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

where L is the depth of the recursion tree

Department of Computer Science

T(n) = n/ 20 +n/ 21 + n/ 22 +n/ 23+ ………. n/ 2logn

Department of Computer Science

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

Department of Computer Science