Analysis of Recursive Algorithms
David Weir (U of Sussex) Program Analysis Term 1, 2015 377 / 606
Recursive Problem Solving
Suitable when a problem instance can be broken into smaller instances of the same problem
Three characteristic phases of recursive problem solving:
Divide: split the problem into smaller similar sub-problems
Conquer: solve each sub-problems by recursion
Combine: solutions to sub-problems combined to give solution to original problem
David Weir (U of Sussex) Program Analysis Term 1, 2015 378 / 606
Example: MergeSort
Divide array of values into two halves — trivial: Θ(1)
Recursively MergeSort each half
Merge two sorted halves into a single sorted array
— takes time: Θ(m)
initial problem : result of recursion : result of merging :
⇓ ⇓
44
22
55
72
8
35
12
60
22
44
55
72
8
12
35
60
8
12
22
35
44
55
60
72
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
379 / 606
MergeSort Algorithm
MergeSort(A, i, j) :
if j > i
let k = ⌈(i + j)/2⌉ MergeSort(A,i,k) MergeSort(A,k +1,j) Merge(A, i, k, j)
Merge(A, i, k, j) takes O(j − i) steps
David Weir (U of Sussex) Program Analysis Term 1, 2015 380 / 606
Complete Computation
44
22
55
72
8
35
12
60
David Weir (U of Sussex) Program Analysis Term 1, 2015 381 / 606
Complete Computation
44
22
55
72
8
35
12
60
44
22
55
72
8
35
12
60
David Weir (U of Sussex) Program Analysis Term 1, 2015 382 / 606
Complete Computation
44
22
55
72
8
35
12
60
44
22
55
72
8
35
12
60
44
22
55
72
8
35
12
60
David Weir (U of Sussex) Program Analysis Term 1, 2015 383 / 606
Complete Computation
44
22
55
72
8
35
12
60
44
22
55
72
8
35
12
60
44
22
55
72
8
35
12
60
44
22
55
72
8
35
12
60
David Weir (U of Sussex) Program Analysis Term 1, 2015 384 / 606
Complete Computation
44
22
55
72
8
35
12
60
44
22
55
72
8
35
12
60
44
22
22
44
55
72
55
72
8
35
8
35
12
60
12
60
44
22
55
72
8
35
12
60
David Weir (U of Sussex) Program Analysis Term 1, 2015 385 / 606
Complete Computation
44
22
55
72
8
35
12
60
44
22
55
72
22
44
55
72
8
35
12
60
8
12
35
60
44
22
22
44
55
72
55
72
8
35
8
35
12
60
12
60
44
22
55
72
35
12
60
David Weir (U of Sussex) Program Analysis Term 1, 2015 386 / 606
8
Complete Computation
44
22
55
72
8
35
12
60
8
12
22
35
44
55
60
72
44
22
55
72
22
44
55
72
8
35
12
60
8
12
35
60
44
22
22
44
55
72
55
72
8
35
8
35
12
60
12
60
44
22
55
72
35
12
60
David Weir (U of Sussex) Program Analysis Term 1, 2015 387 / 606
8
Example: QuickSort
Partitiion array of values around a pivot — takes time: Θ(m)
Recursively QuickSort each half Two halves form single sorted array
— trivial: Θ(1)
initial problem : result of partitioning : result of recursion :
⇓ ⇓
44
22
55
72
8
35
12
60
22
12
8
35
44
60
55
72
8
12
22
35
44
55
60
72
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
388 / 606
QuickSort Algorithm
QuickSort(A, i, j) :
if j > i
k ← Partition(A,i,j) QuickSort(A,i,k −1) QuickSort(A,k +1,j)
Partition(A, i, j) takes O(j − i) steps
David Weir (U of Sussex) Program Analysis Term 1, 2015 389 / 606
Complete Computation
44
22
55
72
8
35
12
60
David Weir (U of Sussex) Program Analysis Term 1, 2015 390 / 606
Complete Computation
44
22
55
72
8
35
12
60
22
12
8
35
44
60
55
72
David Weir (U of Sussex) Program Analysis Term 1, 2015 391 / 606
Complete Computation
44
22
55
72
8
35
12
60
22
12
8
35
44
60
55
72
22
12
8
35
44
60
55
72
David Weir (U of Sussex) Program Analysis Term 1, 2015 392 / 606
Complete Computation
44
22
55
72
8
35
12
60
22
12
8
35
44
60
55
72
22
12
8
35
44
12
8
22
35
44
60
55
72
55
60
72
David Weir (U of Sussex) Program Analysis Term 1, 2015 393 / 606
Complete Computation
44
22
55
72
8
35
12
60
22
12
8
35
44
60
55
72
22
12
8
35
12
8
22
35
60
55
72
55
60
72
12
8
35
55
72
David Weir (U of Sussex) Program Analysis Term 1, 2015 394 / 606
Complete Computation
44
22
55
72
8
35
12
60
22
12
8
35
44
60
55
72
22
12
8
35
12
8
22
35
60
55
72
55
60
72
12
8
8
12
35
55
72
David Weir (U of Sussex) Program Analysis Term 1, 2015 395 / 606
Complete Computation
44
22
55
72
8
35
12
60
22
12
8
35
44
60
55
72
22
12
8
35
12
8
22
35
60
55
72
55
60
72
12
8
8
12
35
55
72
8
David Weir (U of Sussex) Program Analysis Term 1, 2015 396 / 606
Recurrences
Question: How do we calculate the running time of QuickSort and MergeSort?
Answer: Define running time recursively
Let T (n) be the running time for a problem of size n
We will consider three cases: Best-case running time Worst-case running time Expected-case running time
David Weir (U of Sussex) Program Analysis Term 1, 2015 397 / 606
QuickSort: Best-case
Partition performs even split
T (n) can be expressed as a recurrence
T (n) = 2T (n/2) + cn T (1) = c
2 recursive calls on problems of half original size + Θ(n) additional steps
David Weir (U of Sussex) Program Analysis Term 1, 2015 398 / 606
Solving Recurrences
Substitution: Unravel recursion
Try to identify a pattern
David Weir (U of Sussex) Program Analysis Term 1, 2015 399 / 606
Looking for a Pattern
T(n)
= 2Tn+cn 2
= 22Tn+cn+cn 42
= 22Tn+2cn 22
= 22(2Tn+cn)+2cn 23 22
= 23Tn+3cn 23
.
= 2kTn+kcn
2k .
?
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
400 / 606
Computation Tree
T (n) = 2T (n/2) + cn cn
cn cn
22
cncncncn
4444
. . . . . . . . Total is cn for each level of the tree
David Weir (U of Sussex) Program Analysis
Term 1, 2015
401 / 606
Solving Recurrences
T (n) = 2k T n + k cn 2k
How deep can the recursion take us?
n is divided by increasingly larger powers of 2 Stop recursion when problem size reaches 1 Recursion will have ended when k = ⌈log n⌉
n≤1 2⌈log n⌉
Hence let k = Θ(log n) and T (1) = Θ(1) in above recurrence First term is Θ(n)
Second term is Θ(n log n)
T(n) = Θ(nlogn)
David Weir (U of Sussex) Program Analysis Term 1, 2015 402 / 606
QuickSort: Worst-case
Partition performs maximally uneven split T (n) can be expressed as a recurrence
T (n) = T (n − 1) + cn T (1) = c
1 recursive call on problem of with one less value + Θ(n) additional steps
David Weir (U of Sussex) Program Analysis Term 1, 2015 403 / 606
Solving Recurrences
Substitution: Unravel recursion
Try to identify a pattern
T(n) = T(n−1)+cn
= T(n−2)+c(n−1)+cn
.
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
404 / 606
Looking for a Pattern
T(n)
= T(n−1)+cn
= T(n−2)+c(n−1)+cn
= T(n−2)+c(n−1+n)
= T(n−3)+c(n−2)+c(n−1)+cn = T(n−3)+c(n−2+n−1+n)
.
= T(1)+c(1+2+…+n) = Θ(n2)
David Weir (U of Sussex)
Program Analysis Term 1, 2015 405 / 606
Computation Tree
T (n) = 2T (n/2) + cn cn
c(n − 1)
c(n − 2)
c
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
406 / 606
Expected-Case of QuickSort
QuickSort is worst for commonly occurring data sets! Better to select a pivot at random
This gives an expected running time of Θ(n log n) Why?
David Weir (U of Sussex) Program Analysis Term 1, 2015 407 / 606
Randomised QuickSort
Consider partitions of a sequence of length m
Partitions are good if neither subsequence is smaller than m
values arranged in increasing order
4
bad pivots good pivots bad pivots
m good pivots and m bad pivots 22
David Weir (U of Sussex) Program Analysis
Term 1, 2015
408 / 606
Randomised QuickSort (cont.)
Probability that partition is good is 0.5
Thus, on average every second pivot will be good
When good pivot chosen, largest subsequence size is 3 m 4
Hence,averageheightofcomputationtreeis≤2log4 n 3
2log4 n is Θ(logn) 3
Hence expected running time is n log n
David Weir (U of Sussex) Program Analysis Term 1, 2015 409 / 606
Another Recurrence
T(n) = T(n/2) + cn
cn
cn
cn
4
.
2
This tree is also log n deep David Weir (U of Sussex)
Program Analysis
Term 1, 2015
410 / 606
Unravelling Recursion
T(n)
= Tn+cn 2
= Tn+1cn+cn 22 2
= Tn+1+1cn 22 2
= Tn+1+1+ 1cn 23 222
.
= Tn+1+1+ 1 +…+ 1cn
= Θ(n)
2k 222 2k = T(1)+2cn
David Weir (U of Sussex)
Program Analysis Term 1, 2015 411 / 606
A Class of Recurrences
A more general case can be expressed as:
T (n) = qT (n/2) + cn
where q is the number of recursive calls made For q = 1 the solution is Θ(n)
For q = 2 the solution is Θ(n log n) For q > 2 the solution is Θ(nlog2 q)
Note that in these cases the immediate sub-problems have n/2 size
David Weir (U of Sussex) Program Analysis Term 1, 2015 412 / 606
Problem for you
Thisalgorithmfindsmth highestvaluein(ai,…,aj)
QuickSelect(A, m, i , j ) :
Partition(A,i,k,j)
g ← j − k (number of elements ≥ pivot) if m ≤ g then
QuickSelect(A, m, k + 1, j ) else if m = g + 1 then
return A[k] else
QuickSelect(A,m − g + 1,i,k − 1) Give recurrence for worst-case running time
David Weir (U of Sussex) Program Analysis Term 1, 2015 413 / 606
Problem for you
Thisalgorithmfindsmth highestvaluein(ai,…,aj)
QuickSelect(A, m, i , j ) :
Partition(A,i,k,j)
g ← j − k (number of elements ≥ pivot) if m ≤ g then
QuickSelect(A, m, k + 1, j ) else if m = g + 1 then
return A[k] else
QuickSelect(A,m − g + 1,i,k − 1)
Give recurrence for worst-case running time T (n) = T (n − 1) + cn
T (1) = c
David Weir (U of Sussex) Program Analysis Term 1, 2015 413 / 606
Problem for you
Thisalgorithmfindsmth highestvaluein(ai,…,aj)
QuickSelect(A, m, i , j ) :
Partition(A,i,k,j)
g ← j − k (number of elements ≥ pivot) if m ≤ g then
QuickSelect(A, m, k + 1, j ) else if m = g + 1 then
return A[k] else
QuickSelect(A,m − g + 1,i,k − 1) Give recurrence for best-case running time
David Weir (U of Sussex) Program Analysis Term 1, 2015 414 / 606
Problem for you
Thisalgorithmfindsmth highestvaluein(ai,…,aj)
QuickSelect(A, m, i , j ) :
Partition(A,i,k,j)
g ← j − k (number of elements ≥ pivot) if m ≤ g then
QuickSelect(A, m, k + 1, j ) else if m = g + 1 then
return A[k] else
QuickSelect(A,m − g + 1,i,k − 1)
Give recurrence for best-case running time T(n) = T(n/2) + cn
T (1) = c
David Weir (U of Sussex) Program Analysis Term 1, 2015 414 / 606