DIVIDE AND CONQUER Design and

Analysis of
Algorithms
PART I

GENERAL TEMPLATE
BINARY SEARCH
MERGE SORT & QUICK SORT
SOLVING RECURRENCE RELATI ONS
 LOGISTICS

 Instructo r
Prof. Amrinder Arora
amrinder@gwu.edu
Please copy TA on emails
Please feel free to call as well
☺

 Available for study sessions

Science and Engineering Hall
GWU

Algorithms Divide and Conquer - Part I 2

 WHERE WE ARE

Asymptotic
Analysis
NP-
Completeness

D&C

Algorithms
DP

Design Greedy

Applications Graph

B&B

Algorithms Divide and Conquer - Part I 3

 DIVIDE AND CONQUER

 A technique to solve complex problems by breaking into

smaller instances of the problem and combining the res ults
▪ Recursive methodology – Smaller instances of the same type of
problem
 Typically used accompaniments
▪ Induction for proving correctness
▪ Recurrence relation solving for computing time (and/or space)
complexity

Algorithms Divide and Conquer - Part I 4

 D&C – CS, NOT MANAGEMENT/POLITICS

By definition: For D&C, sub

problems must be of same
type.

[ The phrase “D&C” is also used

in other contexts. It may refer
to breaking down a task, but in
Computer Science, D&C is a
formal paradigm]

Algorithms Divide and Conquer - Part I 5

 RECURSION

 A recurs ive algorithm is an algorithm that calls itself on

smaller input.
 Algo rithm sor t (Array a)
Begin
sort (subarray consisting of first half of a)
sort (subarray consisting of second half of a)
do_something_else();
End

Algorithms Divide and Conquer - Part I 6

 RECURRENCE RELATIONS

 Recurrence Relation is a recurs ive formula, commonly used to

analyze the time complexity of recursive algorithms
 For example
▪ T(n) = T(n/2) + T(n/2) + n 2
▪ T(n) = a T(n/b) + f(n)

 Note: Recu rrence Relations have uses outside of time

complexity analysis as well (for example in combinatorics),
but for the purpose of this lecture, this is the main use case.

Algorithms Divide and Conquer - Part I 7

 HOW TO D&C

 Wikipedia says: “…it is often necessar y to replace the o riginal

problem by a more general or complicated problem in order to
get the recursio n going, and there is no systematic method for
finding the proper generalization.”
▪ Refer to this as the “generalization” step
▪ Sometimes counterintuitive that making a “generalization”, that is,
making the problem harder actually helps in solving it!

Algorithms Divide and Conquer - Part I 8

 GENERAL TEMPLATE

d ivid e_ c on qu er (i np ut J )
{
// B as e C as e
if ( si z e of inp ut i s sm all en oug h ) {
s olve di rec t ly an d ret u rn
}

// D ivi de Step
d ivid e J int o o ne or mor e p ar t s J 1 , J 2 ,...

// Rec u rs ive Ca lls

c a ll d ivid e_ c on qu er (J 1 ) to get a s ub so lut io n S1
c a ll d ivid e_ c on qu er (J 2 ) to get a s ub so lut io n S2
...
// M erge Step
M er g e t he s ub so lut io ns S1 , S2,. ..in to a glob al so lut io n S
ret u rn S
}

Algorithms Divide and Conquer - Part I 9

 GENERATE THE RECURRENCE FOR THIS
ALGORITHM..
di vide _ co nque r ( input J (o f s iz e n))
{
// Bas e C as e
i f ( n <= 2) {
s ol ve dire c tly an d re turn // A ss ume this ta ke s a c o nstan t am o unt o f tim e
}

// Div ide Ste p

di vide J into 3 par ts: J 1 o f s iz e n/ 2 J 2 o f si ze n/ 3 and J 3 o f si z e n/ 4

// Re c urs iv e C al ls
c all di vide _ co nque r ( J 1) to ge t a s ubso luti o n S 1
c all di vide _ co nque r ( J 2) to ge t a s ubso luti o n S 2
c all di vide _ co nque r ( J 3) to ge t a s ubso luti o n S 3

// Me rge Ste p
Me rg e the s ubso luti o ns S 1, S 2, S 3 i nto a g lo bal s o luti o n S
// As sume thi s takes a c o ns tant amo unt o f ti me
re turn S
}

Algorithms Divide and Conquer - Part I 10

 NUMBER OF BRANCHES

 Number of subproblems that you create in the “divide” step

 This plays a role in the recurrence relation that is created for
analysis
▪ T(n) = a T(n/b) + f(n)
Here “a” branches, each with size “n/b”, and f(n) time spent in
dividing and merging
▪ Example: T(n) = T(n/2) + 1
1 branch, size half and constant time spent in dividing and merging

Algorithms Divide and Conquer - Part I 11

 GENERAL TEMPLATE – TIME COMPLEXIT Y
VIEW
d ivid e_ c on qu er (i np ut J )
a recursive calls of size
{
// B as e C as e
n/b each. Total time:
if ( si z e of inp ut i s sm all en oug h ) { a T(n/b)
s olve di rec t ly an d ret u rn
Combined time
} in steps other
than recursive
// D ivi de Step calls: f(n)
d ivid e J int o t w o or m ore pa r ts J 1 , J 2, ...

// Rec u rs ive Ca lls

c a ll d ivid e_ c on qu er (J 1 ) to get a s ub so lut io n S1
c a ll d ivid e_ c on qu er (J 2 ) to get a s ub so lut io n S2
...
// M erge Step
M er g e t he s ub so lut io ns S1 , S2,. ..in to a glob al so lut io n S
ret u rn S
}

Algorithms Divide and Conquer - Part I 12

 D&C – EXAMPLE ALGORITHMS

 Binary Search
 Merge Sort
 Quick Sort

Algorithms Divide and Conquer - Part I 13

 BINARY SEARCH

 Search (A, low, high, key)

▪ Mid = (low + high) / 2
▪ Compare A[mid] to key, and look either in lef t half or in right half
 T(n) = T(n/2) + 1

 T(n) = O(log n)

Algorithms Divide and Conquer - Part I 14

 MERGE SORT

 Cl as si c pro blem : G iv en an array, to so rt i t

 G ene raliz a t ion s tep : G iv en an array a nd in dex es i a nd j (s t ar t a nd en d) to
s ort t ha t po rt i on of i t
 A lg ori th m M erge Sort (i np ut : A ,i ,j) {
// Ba se Ca se
if ( j – i < TH R ESH O LD ) {
I ns ert io nSo rt ( A ,i ,j)
Ret u rn
}

// Div ide po rti on

in t k= (i+ j)/ 2

// Re c urs iv e C al ls
M erge Sort ( A ,i ,k)
M erge Sort (A ,k+ 1 ,j)

/ / Me rge C all s
M erge (A ,i, k, k+1 , j)
}

Algorithms Divide and Conquer - Part I 15

 MERGING

 How to merge two lists effectively?

Algorithms Divide and Conquer - Part I 16

 TIME COMPLEXITY OF MERGE SORT

 T(n) = 2T(n/2) + (n)

 Need s ome methods for solving such recurrence equations
▪ Substitution method
▪ Recursion tree method (unfolding)
▪ Master theorem
 T(n) = (n log n)

Algorithms Divide and Conquer - Part I 17

 EXAMPLES OF RECURRENCE RELATIONS

 T(n) = T(n/2) + 1
 T(n) = T(n/2) + n
 T(n) = 2T(n/2) + 1
 T(n) = 2T(n/2) + n
 T(n) = 3T(n/2) + n
 T(n) = 3T(n/2) + n log n
 T(n) = T(sqrt(n)) + 1

// Base Case is usually T(1) = 1,

// You can use any T(a) = b, where a and b are both specific
numbers, such as T(100) = 2.

Algorithms Divide and Conquer - Part I 18

 SOLVING RECURRENCE RELATIONS

 Examples:
▪ T(n) = 2 T(n/2) + cn
T(n) = O (n log n)
▪ T(n) = T(n/2) + n
T(n) = O (n)

 3 General Approaches:
▪ Recursion tree method (unfold and reach a pattern)
▪ Substitution method (Guess and Prove)
▪ Master theorem

Algorithms Divide and Conquer - Part I 19

 UNFOLDING METHOD

 Given T(n) = T(n/2) + n

 Then T(n) = T(n/2) + n
= T(n/4) + n/2 + n
= T(n/8) + n/4 + n/2 + n

= ..

Algorithms Divide and Conquer - Part I 20

 UNFOLDING METHOD

 Given T(n) = 2T(n/2) + n^2

 Then T(n) = 2T(n/2) + n^2
= 2^2 T(n/4) + n^2/2^2 + n^2

= ..

Algorithms Divide and Conquer - Part I 21

 SUBSTITUTION METHOD FOR MERGE SORT

 Given T(n) = 2 T(n/2) + cn

 We fir st “guess ” that the solution is O(n log n)
 To prove this using induction, we first assume T(m) <= km log
m for all m < n
 Then T(n) = 2 T(n/2) + cn
<= 2 kn/2 log (n/2) + cn
= kn log n – (k – c)n // log (n/2) = log n – 1
<= k n log n, as long as k >= c

Algorithms Divide and Conquer - Part I 22

 SUBSTITUTION METHOD FOR MERGE SORT

 Given T(n) = 11 T(n/10) + 5n

 We fir st “guess ” that the solution is O(n log n)
 To prove this using induction, we first assume:
T(m) <= 100 m log m for all m < n
 Then T(n) = 11 T(n/10) + 5n
<= 11 100 (n/10) log (n/10) + 5n
….
<= 110 n log n
….
INCORRECT CONCLUSION!!!

<= 110 n log n Must prove the algebraic

= O(n log n) inequality, before drawing
any asymptotic conclusion!

Algorithms Divide and Conquer - Part I 23

 MASTER THEOREM FOR SOLVING
RECURRENCE RELATIONS
Only applies to Recur rence Relations of fo llow ing type

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

Fo r exa mpl e, M T doe s no t a ppl y S( n ) = S(n /2) + S(n /3) + f(n )

 Cas e 1. If f( n) = O (n c ) w he re c < lo g b a, the n T(n ) = θ(n ^l og b a )

f(n) is POLYNOMIALLY smaller than n^log b a
 Cas e 2. If it is true, for some const ant k ≥ 0, t hat f( n) = θ(n c lo g k
n ) w he re c = lo g b a, the n T(n ) = θ(n c lo g k +1 n )
▪ f(n) is POLYNOMIALLY equal to n^log b a
 Cas e 3. If it is true that f( n) = Ω(n c ) where c > lo g b a, the n T(n ) =
θ( f(n ))
▪ f(n) is POLYNOMIALLY larger than n^log b a

Algorithms Divide and Conquer - Part I 24

 MASTER THEOREM – INTUITION

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

➔T(n/b) = a T(n/b^2) + f(n/b)
➔T(n) = a [a T(n/b^2) + f(n/b)] + f(n)
➔T(n) = a^2 T(n/b^2) + a f(n/b) + f(n)
…
If we unfold this k times, we get an expression like:
T(n) = a k T(n/b k ) + f(n) + a f(n/b) + … + a k f(n/b k )

Then, for k ≈ log b n, T(n/b k ) will be a small constant, and we can

assume T(n/b k ) = 1.
Then, T(n) = a^(log b n) + f(n) + af(n/b) + … + a k f(n/b k )
= n^(log b a) + f(n) + af(n/b) + … + a k f(n/b k )
We note that there are about log b n terms.

Algorithms Divide and Conquer - Part I 25

 MASTER THEOREM – INTUITION (CO NT.)

T(n) = n^(log b a) + f(n) + af(n/b) + … + a k f(n/b k )

We observe that:
• If f(n) is very small, say a constant, then the first term dominates
• If f(n) =  (n^(log b a)), then the T(n) = f(n) log n.
// The log n factor arises because there are ~ log n terms
• If f(n) is too large, then f(n) terms dominate

Algorithms Divide and Conquer - Part I 26

 APPLYING MASTER THEOREM TO MERGE
SORT RECURRENCE

T(n) = 2 T(n/2) + c n
In this case:
• a=b=2
• f(n) = c n
• log b a = 1
• n^(log b a) = n
So, f(n) =  (n^(log b a))
Therefore, by Master Theorem,
T(n) = (f(n) log n)
That is, T(n) = (n log n)

Algorithms Divide and Conquer - Part I 27

 APPLYING MASTER THEOREM TO OTHER

T(n) = 3 T(n/2) + n
In this case:
• a = 3, b = 2
• f(n) = n
• log b a = log 2 3.
• 2^x = 3.
• 2^1 < 3. and 2^2 > 3.
• 1 < log_2 (3) < 2
• f(n) is O of n^ log 2 3

• By MT: T(n) = n^ log 2 3. Case 1

Algorithms Divide and Conquer - Part I 28

 APPLYING MASTER THEOREM TO OTHER

T(n) = 5 T(n/2) + n 3

Algorithms Divide and Conquer - Part I 29

 APPLYING MASTER THEOREM TO OTHER

T(n) = 5 T(n/2) + n 3
In this case:
• a=5
• b=2
• f(n) = n 3

• Which term is larger? f(n) or n^log_b(a)

• T(n) = n 3 // By Case 3

Algorithms Divide and Conquer - Part I 30

 PRACTICE QUESTIONS

 T(n) = 5 T(n/2) + n 3
▪ T(n) = n 3
 T(n) = 5 T(n/2) + n 2
▪ T(n) = n log 2 5
 T(n) = 5 T(n/2) + n 2 log n
▪ T(n) = n log 2 5
 T(n) = 5 T(n/2) + n 3 log n
▪ T(n) = n 3 log n

Algorithms Divide and Conquer - Part I 31

 PRACTICE QUESTIONS (CASE 2)

T(n) = T(n/2) + f(n) (Binar y Search) T(n) = T(n/6) + log

T(n) = log n log k n
====================== In this case:
T(n) = T(n/6) + log k n • a = 1, b = 6
In this case: • f(n) = log k n
• log b a = 0
• a = 1, b = 6
• f(n) = log k n • n^(log b a) = n^0
• log b a = 0 Master Theorem
• n^(log b a) = n^0
(Case 2),
So, f(n) =  (n^(log b a)) T(n) = (f(n) log
n)
Therefore, by Master Theorem (Case 2),
That is, T(n) =
T(n) = (f(n) log n) (log n log log k
That is, T(n) = (lo g k+1 n) n)

Algorithms Divide and Conquer - Part I 32

 APPLYING MASTER THEOREM TO ANOTHER
RECURRENCE RELATION

T(n) = 2 T(n/2) + c n log n

In this case:
• a=b=2
• f(n) = c n log n
• log b a = 1
• n^(log b a) = n
So, f(n) =  (n^(log b a))
Therefore, by Master Theorem,
T(n) = (f(n) log n)
That is, T(n) = (n log^2 n)

Algorithms Divide and Conquer - Part I 33

 QUICKSORT

 Select a “par tition” element

 Partition the array into “left” and “right” portions (not
necessarily equal) based on the partition element
 Sor t the left and right sides

 An inver ted view o f mergesor t – spend time upfront

(partition), no need to merge later.

Algorithms Divide and Conquer - Part I 34

 QUICKSORT – THE PSEUDO CODE

 quicksor t(A,p,r)
if (p < r) {
q = par tition (A,p,r)
quicksor t(A,p,q-1)
quicksor t(A,q+1,r)
}

Algorithms Divide and Conquer - Part I 35

 QUICKSORT (THE TRIVIA CLUB VIEW)

 Invented in 1960 by C. A. R. Hoare

 Mo re widely used than any other sor t
 A well-studied, not difficult to implement algorithm
 R. Sedgewick – 1975 Ph.D. thesis at Stanford Univ. –
Analysis and Variations of QuickSort

Who said: “Elementary, My Dear Watson”?

Algorithms Divide and Conquer - Part I 36

 QUOTES, QUOTES

 “There are two ways of constructing a software design: One

way is to make it so simple that there are obviously no
deficiencies, and the other way is to make it so complicated
that there are no obvious deficiencies . The first metho d is far
more difficult.”
 “We should forget about small efficiencies, s ay about 97% of
the time: premature optimization is the root of all evil.”

Algorithms Divide and Conquer - Part I 37

 EXAMPLE RUN

 -23, 100, 1 , 3, 5, 18, 0, 31, 102, 34

 Partition element: -23
 []. -23 [100, 1 , 3, 5, 18, 0, 31, 102, 34]

 -23, 100, 1 , 3, 5, 18, 0, 31, 102, 34

 Partition element: 5
 [-23, 1, 3, 0]. 5 [100, 18, 31 , 102, 34]

Algorithms Divide and Conquer - Part I 38

 EXAMPLE PARTITION RUN

 23, 100, 1 , 3, 5, 18, 0, 31, 102, 34, 21, 28, 51, 90, 4
 Partition element: 18
 [4,0, 1, 3, 5] 18 [100, 31, 102, 34, 21, 28, 51, 90, 23]

Algorithms Divide and Conquer - Part I 39

 CENTRAL PROBLEM IN QUICKSORT

 How to find a good partition element

 How to partition (efficiently)
 Partition array so that:
▪ Some partitioning element (q) is its final position
▪ Every element smaller than q is to the lef t of q
▪ Every element larger than q is to the right of q

 Sedgwick states that “improving QuickSort is the better

mousetrap of co mputer science”

Algorithms Divide and Conquer - Part I 40

 QUICKSORT – TIME COMPLEXITY ANALYSIS

 T(n) = T(n 1 ) + T(n 2 ) + O(n)

Where n 1 + n 2 = n – 1
 So it all depends upon the kind of the s plit, and split will
likely not be the same each time.
 Worst cas e – very bad split: O(n 2 )
 Best case – good split: O(n log n)
 Average case – where does that fit?

http://mathworld.wolfram.com/Quicksort.html

Algorithms Divide and Conquer - Part I 41

 OPEN QUESTIONS

How l ong w ill the algor ithm take?

functi on sum ( inte ger a) {
if (a == 1) exit;
if (a is odd) {
a = 3a + 1
} else {
a = a/2
}
}

Tri chotomy – E xtende d

Gi ven tw o funct ions f(n) and g( n) , both s trictl y increas ing w ith n,
is it po ss ible t hat f( n) and g(n) cannot be compar ed
asymptotically?

Algorithms Divide and Conquer - Part I 42

 READING ASSIGNMENTS

1. Median Finding
(Textbook § 4.6)
2. Closest pair of
points algorithm
(Textbook § 4.7)
3. Strassen’s
algorithm for
matrix
multiplication
We already have quite a few people who know
(Textbook § 4.8) how to divide. So essentially, we are now
https :/ / yo utu.be / 1A I vli z Go 7Y
looking for people who know how to conquer.
Algorithms Divide and Conquer - Part I 43
 WHERE WE ARE

Asymptotic
Analysis
NP-
Completeness

D&C

Algorithms
DP

Design Greedy

Applications Graph

B&B

Algorithms Divide and Conquer - Part I 44

More D&C
in Next
Lecture