Recurrences and Running Time
• An equation or inequality that describes a function in
terms of its value on smaller inputs.
T(n) = T(n-1) + n
• Recurrences arise when an algorithm contains recursive
calls to itself
1
Example Recurrences
• T(n) = T(n-1) + n Θ(n2)
– Recursive algorithm that loops through the input to
eliminate one item
• T(n) = T(n/2) + c Θ(lgn)
– Recursive algorithm that halves the input in one step
• T(n) = T(n/2) + n Θ(n)
– Recursive algorithm that halves the input but must
examine every item in the input
• T(n) = 2T(n/2) + 1 Θ(n)
– Recursive algorithm that splits the input into 2 halves
and does a constant amount of other work
2
Applications
• Divide and Conquer Algorithms
• Used to analyze recursive algorithms like:
𝑇(𝑛)=2𝑇(𝑛/2)+𝑂(𝑛)→ 𝑂(𝑛log𝑛)
• Merge Sort:
Binary Search: 𝑇(𝑛)=𝑇(𝑛/2)+𝑂(1) → 𝑂(log𝑛)
•
QuickSort: 𝑇(𝑛)=2𝑇(𝑛/2)+𝑂(𝑛) (average case)
•
→ 𝑂(𝑛log𝑛)
3
Recurrent Algorithms
BINARY-SEARCH
• for an ordered array A, finds if x is in the array A[lo…hi]
1 2 3 4 5 6 7 8
Alg.: BINARY-SEARCH (A, lo, hi, x)
2 3 5 7 9 10 11 12
if (lo > hi)
return FALSE mid
lo hi
mid (lo+hi)/2
if x = A[mid]
return TRUE
if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x)
if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x)
4
Example
• A[8] = {1, 2, 3, 4, 5, 7, 9, 11}
– 1 lo =2 1 hi
3 = 48 x5 = 76 7 8
1 2 3 4 5 7 9 11 mid = 4, lo = 5, hi = 8
5 6 7 8
1 2 3 4 5 7 9 11 mid = 6, A[mid] = x
Found!
5
Another Example
• A[8] = {1, 2, 3, 4, 5, 7, 9, 11}
– lo = 1 hi = 8 x=6
1 2 3 4 5 6 7 8
1 2 3 4 5 7 9 11 mid = 4, lo = 5, hi = 8
low high
1 2 3 4 5 7 9 11 mid = 6, A[6] = 7, lo = 5, hi = 5
low high
1 2 3 4 5 7 9 11 mid = 5, A[5] = 5, lo = 6, hi = 5
NOT FOUND!
1 2 3 4 5 7 9 11
high low
6
Analysis of BINARY-SEARCH
Alg.: BINARY-SEARCH (A, lo, hi, x)
if (lo > hi) constant time: c1
return FALSE
mid (lo+hi)/2 constant time: c2
if x = A[mid] constant time: c3
return TRUE
if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x)
same problem of size n/2
if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi,same
x) problem of size n/2
• T(n) = c +T(n/2)
– T(n) – running time for an array of size n
7
Methods for Solving Recurrences
•Substitution method
•Recursion tree method
•Master method
8
The substitution method
1. Guess a solution
2. Use induction to prove that the
solution works
9
10
Substitution Method
• T(n)= T(n-1) + n T(1)=1
• T(n) = T(n-1) + 1
• T(n) = 5T(n-1) T(1)=5
11
12
13
14
Substitution Method
• Example 1
• T(n) = T(n-1)+c if n>1
• =c if n=1
• Example 2
• T(n) = T(n/2)+c if n>1
• =1 if n=1
• Example 3
• T(n) = n * T(n-1) if n>1
• 1 if n=1
15
T(n) = c + T(n/2)
T(n) = c + T(n/2) T(n/2) = c + T(n/4)
= c + c + T(n/4) T(n/4) = c + T(n/8)
= c + c + c + T(n/8)
Assume n = 2k
T(n) = c + c + … + c + T(1)
k times
= clgn + T(1)
= Θ(lgn)
16
T(n) = n + 2T(n/2) Assume: n =
2k
T(n) = n + 2T(n/2) T(n/2) = n/2 + 2T(n/4)
= n + 2(n/2 + 2T(n/4))
= n + n + 4T(n/4)
= n + n + 4(n/4 + 2T(n/8))
= n + n + n + 8T(n/8)
… = in + 2iT(n/2i)
= kn + 2kT(1)
= nlgn + nT(1) = Θ(nlgn)
17
The recursion-tree method
Convert the recurrence into a tree:
– Each node represents the cost incurred at various
levels of recursion
– Sum up the costs of all levels
Used to “guess” a solution for the recurrence
18
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) lg n 2
2 W (1) n 2
2
n n 2
2 2
O(n) n O(n) 2n
i 0 2i i 0 i 0 1 1
2
W(n) = O(n2)
19
Example 2
E.g.: 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 3
cn 2 n log4 3 O(n 2 )
i 0 16 i 0 16
1
T(n) = O(n2) 16 20
Example 3 (simpler proof)
W(n) = W(n/3) + W(2n/3) +
n
• The longest path from the root to a
leaf is:
n (2/3)n (2/3)2 n … 1
• Subproblem size hits 1 when 1=
(2/3)in i=log3/2n
• Cost of the problem at level i = n
• Total cost:
lg n
W (n) n n ... n(log 3/ 2 n) n O (n lg n)
3
lg
W(n) = O(nlgn) 2
21
Example 3
W(n) = W(n/3) + W(2n/3) +
n
• The longest path from the root to a
leaf is:
n (2/3)n (2/3)2 n … 1
• Subproblem size hits 1 when 1=
(2/3)in i=log3/2n
• Cost of the problem at level i = n
• Total cost:
(log3 / 2 n ) 1
W (n) n n ...
i 0
n 2(log3 / 2 n ) W (1)
log3 / 2 n
lg n 1
n 1 nlog3 / 2 2 n log 3/ 2 n O (n) n
lg 3 / 2
O (n)
lg 3 / 2
n lg n O (n)
i 0
W(n) = O(nlgn)
22
Master’s method
• for solving recurrences of the form:
n
T (n) aT f (n)
b
where, a ≥ 1, b > 1, and f(n) > 0
23
Examples
T(n) = 2T(n/2) + n
a = 2, b = 2, log22 = 1
Compare nlog22 with f(n) = n
f(n) = (n) Case 2
T(n) = (nlgn)
24
Examples
T(n) = 2T(n/2) + n2
a = 2, b = 2, log22 = 1
Compare n with f(n) = n2
f(n) = (n1+) Case 3 verify regularity cond.
a f(n/b) ≤ c f(n)
2 n2/4 ≤ c n2 c = ½ is a solution (c<1)
T(n) = (n2)
25
Examples (cont.)
T(n) = 8T(n/2) +n^2
a = 8, b = 2, log28 = ?
26
Examples
T(n) = 3T(n/4) + nlgn
a = 3, b = 4, log43 = 0.793
Compare n0.793 with f(n) = nlgn
f(n) = (nlog43+) Case 3
Check regularity condition:
3(n/4)lg(n/4) ≤ (3/4)nlgn = c f(n), c=3/4
T(n) = (nlgn) 27
Examples
T(n) = 2T(n/2) + nlgn
a = 2, b = 2, log22 = 1
• Compare n with f(n) = nlgn
– seems like case 3 should apply
• f(n) must be polynomially larger by a factor of n
• In this case it is only larger by a factor of lgn
28
Feature Substitution Method Recurrence Tree Method Master Method
Expands the recurrence Provides direct asymptotic
Solves recurrence by
into a tree structure and solutions based on a
Definition guessing a bound and
sums up costs at each predefined formula.
proving it via induction.
level.
Compares the recurrence
Assume a solution, Draws a recursion tree,
to the form T(n)=aT(n/b)
substitute into the calculates work done at
Approach +f(n)T(n) = aT(n/b) + f(n)
recurrence, and use each level, and sums the
and applies predefined
induction to verify. work.
cases.
When visualizing the When the recurrence fits
When an exact or tight
Best Use Case recurrence helps in the form T(n)=aT(n/b)
bound is needed.
identifying patterns. +f(n)T(n) = aT(n/b) + f(n).
Can be time-consuming Requires expansion and
Quick and direct if the
Complexity and requires an educated summation, which can be
recurrence fits the form.
guess. tedious.
Expanding
Applying Master Theorem:
T(n)=2T(n/2)+O(n)T(n) = T(n)=2T(n/2)+O(n)T(n) =
a=2a=2, b=2b=2,
2T(n/2) + O(n) → Assume 2T(n/2) + O(n) gives a tree
Example Recurrence f(n)=O(n)f(n) = O(n) →
T(n)=O(nlogn)T(n) = O(n \ with depth logn\log n,
Case 2 → O(nlogn)O(n \
log n), prove via induction. summing work gives
log n).
O(nlogn)O(n \log n).
Not applicable if
Requires a correct guess Tedious for deep recursion
Limitations recurrence doesn't fit the
for induction to work. trees. 29
standard form.
