Chapter 4

Divide and conquer

Three steps discussed earlier

(1) Divide
(2) Conquer
(3) Combine

When the subproblem is large enough to solve recursively it is called the recursive case.

Once the subproblems become small enough that we no longer recurse, we say that the recursion
“bottoms out” and we have gotten down to the base case.

Some times there are additional subproblems that are not just smaller instances of the original
problem. Solving these subproblems are considered to be a part of the combine step.

Recurrences

Recurrences give a natural way to characterize the run time of divide and conquer algorithms.

A recurrence is an equation or inequality that describes a function in terms of its value on smaller
inputs

Example: T (n) is the worst-case running time of MERGE_SORT

Whose solution was found using a recursive tree to be Θ(n lg n)

Three methods to solve recurrences are discussed –

(1) Substitution method – we guess a bound and use mathematical induction to prove it is
correct
(2) Recursion tree method – converts the recurrence into a tree where each node represents
the cost incurred at various levels of the recursion.
(3) Master method – provides bounds for recurrences of the form T ( n )=aT ( n/b ) + f (n),
where a ≥ 1 ,b ≥ 1

A recurrence of the form of the equation above characterises a divide and conquer algorithm that
creates a number of subproblems, of 1/b the size of the original problem.

Sometimes recurrences are given as inequalities, in such cases we find the solution using Ο –
notation or Ω – notation, depending on the inequality sign.

Technicalities in recurrences

Certain technical details are neglected when recurrences are solved.

Ex: if MERGE_SORT is called for n elements where n is odd, the size of the subproblems are ceil( n /2)
and floor(n /2). Neither size is n /2 since it is not an integer when n is odd.
So, the real recurrence is

T ( n )=Θ(1) for sufficiently small n

For convenience, statements on the boundary conditions of recurrence are omitted and the value of
T (n) is assumed to be constant for small n
The recurrence for MERGE_SORT is mostly stated as

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

Without explicitly giving value for small n

This is because although changing T (1) changes the exact solution, it does not affect the order of
growth.

So, in solving recurrences floors, ceiling and boundary conditions are mostly ignored.

Whether this is okay is determined later.

The maximum subarray problem

Problem

You have an opportunity to invest in Volatile Chemical Corporation. You can only buy one unit of
stock at one time and sell it at a later date. Buying and selling can take place after the end of trading
for that day. The stock prices for the entire timeline from first to last day is known.

Goal: maximize profits.

Incorrect strategies

1: buy at lowest possible price sell at highest possible price – not always possible as can be seen in
above example. Date of highest price before date of lowest price.

2: find the lowest possible price, then work through the right to find the highest later price. Find the
highest price, work through the left to find lowest prior price. Compare profits for both cases.
Not always accurate. Counter example below:

Brute force solution

Try every pair of buy and sell dates in which buy date lies before sell date.

For n days there are (n2 ) such pairs of dates. (n2 ) is Θ(n )
2

Best case if we can evaluate all pairs of dates in constant time so,

This approach would take Ω(n2)

A transformation – look at the problem in a different way.

We need to find the sequence of days where the net change in stock price between first and last day
is max.

So, instead of looking at daily prices, look at change in prices. Such that,

change on day i= price ( i )− price(i−1)

Change in price on day i, for each day can be taken as an array.

We now need to a non-empty, contiguous subarray of A whose values have largest sum.

This is the maximum subarray problem.

However, we still need to check (n−1

2 )
2
=Θ(n ) subarrays for a period on n days.

Though, computing the cost of one subarray ∝ length of subarray,

Computation can be arranged such that each subarray takes Ο(1) time.

Ex: computing all the subarrays starting at one index, then next and so on.

For any one index, first itself, then itself + next, then further add next and so on till end.

Solution using divide and conquer

Divide and conquer suggests that the array be divided into two subarrays as equal as possible.

A[low .. high ] is divided into two subarrays A[low .. mid ] and A[mid +1 ..high]
Any contiguous subarray A[i.. j] of A[low .. high] will lie

1. Entirely in subarray A[low .. mid ]; low ≤ i≤ j ≤ mid

2. Entirely in subarray A[mid +1 ..high]; mid <i≤ j ≤ high
3. Crossing the midpoint; low ≤ i≤ mid < j ≤ high
Thus, max subarray of A[low .. high] lies in one of these three places

So, the max subarray of A[low .. high] is the subarray lying in region 1,2 or 3 with the greatest sum.

Maximum subarrays of A[low .. mid ] and A[mid +1. . high] are found recursively.

Finding the maximum subarray crossing the midpoint is not a smaller instance of original problem. It
is a different problem as there is the added restriction that it must cross the midpoint.

This subarray of region 3 is itself made up of two subarrays

A [ i.. mid ] ∧A [mid +1.. j]; low ≤ i≤ mid < j< high
so, we need to find the 2 maximum subarrays of the above form and combine them to get max
subarray of region 3.

The maximum of the maximum subarrays found in 1,2 and 3 is the solution.

Complexity:

Each iteration of the for loop

take Θ(1)

iterations in first loop:

mid−low +1

iterations in second loop:

high−mid
Total iterations:

high−low +1=n
So, Θ(n)

Line 1: base case – subarray with just one element

Analysing divide and conquer algorithm

Assumption: n is the power of 2

Base case: n=1

Line 1 and 2: constant time

So T ( 1 )=Θ (1)

Recursive case: n>1

Line 1 and 3: constant

Line 4 and 5: T (n/2) each

Line 6: already seen that it is Θ(n)

Line 7 – 11: Θ(1)

T ( n )=Θ (1 )+2 T ( n / 2 )+Θ ( n ) +Θ(1)

¿ 2 T ( n/2 ) +Θ(n)
Combining base case and recursive case

Kadane’s algorithm for maximum contiguous subarray

Start at the left end progress to the right, while keeping track of the maximum subarray seen so far.

Maximum subarray of A[1. . j+ 1] is either the maximum subarray of A[1. . j] or maximum

subarray of A [ 1.. j ] + A [ j+1]

Pseudocode:

Strassen’s method for matrix multiplication

Normal method

let A=(a ij ) and B=(bij ) be two n × n matrices

if C= A ⋅ B

then,
k=n
c ij =∑ aik b kj
k=1

We need to compute n2 matrix entries each of which is the sum of n elements

 Complexity

Each of the for loops run n times

Statement 7 takes Θ(1) time

So, the procedure takes Θ(n3 ) time

Simple divide and conquer algorithm

Assumption: n is to the power of 2 in each of the n × nmatrix

The matrices A and B will be divided into 4 n /2 ×n /2 matrices.

Suppose A , B and C are partitioned into four n /2 ×n /2

A 11 A 12 B11 B 12 C11 C 12
A=
( A 21 A 22 )
, B=
( B21 B 22 )
, (
C=
C21 C 22 ) …( 4.9)

C= A ⋅ B can be written as
C 11 C12 A A 12 B 11 B12
( C 21 C22 )(
= 11 ⋅
)(
A 21 A 22 B21 B22 )
Which corresponds to 4 equations

C 11= A11 ⋅ B11 + A 12 ⋅ B21

C 12=A 11 ⋅B 12+ A12 ⋅B22

C 21=A 21 ⋅ B11 + A22 ⋅B 21

C 11= A 21 ⋅B 12+ A22 ⋅B 22

Each of these equations specify 2 matrix multiplications of the n /2 ×n /2 matrices and 2 additions.

The multiplications can be solved recursively in divide and conquer.

How to partition A , B and C ? In line 5

If we create 12 new n /2 ×n /2 matrices, Θ(n 2) time would be spent copying values

Partitioning can be done without copying entries. We can use index calculations.

The submatrix is identified by a range of row and column indices of the original matrix. Then line 5
only take Θ(1) time.

This representation is slightly different, but it is glossed over for simplicity.

Running time:

Base case: n=1

Line 4: just one scalar multiplication so T ( 1 )=Θ (1)

Recursive case: n>1

Line 5: Θ(1) time using index calculations, Θ(n 2) if copied onto new matrix

Line 6-9: 8 recursive calls. 8 T (n/2), also 4 matrix additions which takes Θ(n 2) time

So,

T ( n )=Θ (1 )+ 8T ( n/2 ) +Θ ( n2 )=8 T ( n/2 )+ Θ(n2 )

If we would have copied the matrix instead of index partitioning, the recurrence would stay the
same
The solution to the recurrence is T ( n )=Θ(n3 )

Strassen’s method

This method makes the recursive tree a little less bushy, so instead of 8 recursive multiplications of
n /2 ×n /2 matrices there are only 7.
Cost of removing 1 recursive multiplication results in several new additions of n /2 ×n /2 matrices.
But it will still be a constant number of additions and will be subsumed by the Θ notation,

Additions of n2 / 4 elements each took Θ(n 2 /4) time which was subsumed to Θ(n 2) time. The
notation subsumes the factor.

Steps: (this method is not obvious)

1. Divide the input matrices A , B and output matrix C into n /2 ×n /2 submatrices. This takes
constant time using index calculations.
2. Create 10 matrices S1 , S 2 , S 3 … S 10 each of which is n /2 ×n /2 submatrices, and should be
the sum or difference of 2 matrices created in step 1. This takes Θ(n 2) time.
3. Using the submatrices created in step 1 and step 2 recursively compute 7 matrix products
P1 , P2 , P 3 … P7. Each Pi is an n /2 ×n /2 matrix.
4. Compute desired submatrices C 11 ,C 12 , C 21 , C22 of the result matrix C by adding or
subtracting various combinations of the Pi matrices. We can compute all 4 in Θ(n 2) time.

Recurrence equation

Base case: T ( 1 )=Θ (1) as before. Only a scalar multiplication which take constant time.

Recursive case: step 1,2,4 takeΘ(n 2) time. Step 3 performs seven multiplications of n /2 ×n /2
matrices. So,

One matrix multiplication was traded off for a constant number of matrix additions.

This leads to a lower asymptotic running time.

The steps

The 10 submatrices created in step 2 are

Since we need to add or subtract 10 n /2 ×n /2matrices, this takes Θ(n 2) time

In step 3, we recursively multiply n /2 ×n /2 matrices 7 times to compute the following n /2 ×n /2

matrices

The RHS just shows what the products are equal too. Only the middle operations are performed
recursively

Step 4 constructs the results as follows

(1)

Expanding shows that it is right

(2)

(3)

(4)

The substitution method for solving recurrences

https://brilliant.org/wiki/the-substitution-method-for-solving-recurrences/

Substitution method comprises two steps –

1. Guess the form of the solution

2. Use mathematical induction to find the constants and prove that the solution works.
Substitution method can be used to establish an upper or lower bound on the recurrence

After guessing the form of the solution:

1. Assume that the hypothesis is true for m<n

2. Use this assumption to prove the hypothesis is true for n
3. Prove true for base case

Example:

for recurrence T ( n )=2 T ( [ n/2 ] ) +n

prove T ( n )=Ο(n lg n)

Hypothesis: for some n> n0, T ( n ) ≤ c nlg n , where c is a constant

Proof:

Assume that the hypothesis is true for m<n

For m=[n/2]

T ( [ n /2 ] ) ≤ c [ n /2 ] lg( [ n/2 ] )

⇒ 2 T ( [ n /2 ] ) +n ≤ 2 c [ n/2 ] lg ( [ n/2 ] ) +n

This is used to prove the hypothesis for n

T ( n )=2 T ( [ n/2 ] ) +n ≤ 2c [ n/2 ] lg ( [ n/2 ] ) +n

≤ c n lg ( n2 )+ n=c n lg n−c nlg 2+n

¿ c n lgn−c n+ n
c n lg n−c n+n<c n lgn , for c >1
Using this we get

T ( n ) ≤ c nlg n , for c>1

Hence the hypothesis is proved, as long as c >1

Now prove the base case:

T ( 1 )=1
c ( 1 ) lg 1=0<T (1)
So not true for T ( 1 )

T ( 2 ) =2 ( 1 ) +2=4< c ( 2 ) lg ( 2 )=2c , for c ≥ 2

So, it is proved that T ( n )=Ο(n lg n)

As T ( n ) ≥ c nlg n where c ≥2 and n0 >1 which is definition for O notation

Sometimes for a correct asymptotic bound, the math fails to work out.
Frequently this is because the inductive hypothesis is not strong enough

This can be overcome by changing the guess by subtracting a lower order term from it

Wrong proof for T ( n )=O(n) for the example above

Change variable to get an easier recurrence.

Example: pg. 87

The recursion tree method for solving recurrences

 In a recursion tree, each node represents the cost of a single subproblem 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,
 then we sum all the per-level costs to determine the total cost of all levels of the recursion.

A recursion tree is best used to generate a good guess, which you can then verify by the substitution
method.
It’s okay to be sloppy since we will verify our guess later.
 Like assuming n is the power of something
 Ignoring floors and ceilings

For example:

Try to find a good guess for the solution of recurrence –

Start by finding upper bound

Since floors and ceiling usually do not matter

Recursion tree can be created for T ( n )=3 T ( n /4 ) +c n2 instead example of sloppiness
We assume that n is an exact power of 4 example of sloppiness

Recursion tree is drawn below

Root – cost incurred at top level recursion

Children – cost of the subproblems of size n /4

Because subproblem sizes decrease by a factor of 4 each time we go down one level, we eventually
must reach a boundary condition.
At a depth i the sub problem size ¿ n /4i

The boundary is when the subproblem size hits 1, so i=log 4 n

The tree has log 4 n+1 levels

Next determine cost at every level

no . of nodes at depthi=3 i
 2
cost of node at depth i=c ( n/ 4i )
cost at every level=no . of nodes at level × cost of each node at that level
2
¿ 3i c ( n/4 i ) =( 3/16 )i c n2
At the bottom level

no . of nodes=3log n =nlog 3
4 4

cost of each node=T (1)

cost of level=nlog 3 T ( 1 )=Θ(n log 3 )

4 4

Cost at every level is added up

To make it less messy, we can use an infinite decreasing geometric series as upper bound
( sloppy)
So instead we have

Thus, the guess T ( n )=Ο(n2 )

For the recurrence

If T ( n )=Ο(n2 ) is really the upper bound, then Ω( n2) is the lower bound
Why? Because the first recursive call contributes a cost of Θ ( n2 ) , so Ω(n2) must be a lower bound
for the recurrence.

This can be verified using substitution method

We want to show that T ( n ) ≤ d n2, for some constant d >0 using the same constant c >0 as before,

Hence proved

Example:

Again, the ceiling and the floor functions are omitted

As before, we let c represent the constant factor in the Ο(n) term

On adding values at every level of the recursion tree we get c n for every level

The longest simple path from the root to the leaf is

n →(2/3)n→ ( 2/3 )2 n→ … →1

( 2/3 )k n=1
⇒ k=log3 / 2 n

The cost is at most ¿ no . of levels ×the cost of each level=Ο ( c n log 3/ 2 n ) =Ο(n lg n)

Not every level in the tree contributes cn

Moreover, as we go down from the root, more and more internal nodes are absent.
Consequently, levels toward the bottom of the recursion tree contributes less than c n to the total
cost.
But we are just trying to come up with a guess to verify in the substitution method, so its okay.

Substitution method to verify that T ( n )=Ο(n lg n)

We show that T ( n )< d n lg n, where d is a suitable positive constant

The master theorem

Lots of examples in pg. 95 and 96 of book