Divide and Conquer

General Method
Now she tells us!

T (n) = T(1) for n = 1
aT(n/b)+f(n) for n > 1

Do the expansions (book calls this the substition method). The text notes,
it can be shown that

^log_ba

j=1 to k

^log_ba

Use this with the homework:
T(n) = 8 T(n/2) + n³
Hint: The solution contains a term cn³log₂n.

How does this compare? ?

Divide and Conquer

Divide

divided, l*k=n

solve

Conquered

T(n) = g(n) for n small (immediately solve the problem)
lT(n/l)+f(n) otherwise

g(n) = time to solve small problem instances (could be constant)

f(n) = time for divide and conquer operations

Ex. Binary search: (assume a sorted array or complete binary search tree)
l = 2 g(n) = c₂ f(n) = c₁

T(n) = O(log n) (Thm. 3.2 page 135 of text)

Mergesort

Pn unsorted

P¹_n/2 and P²_n/2

Sort (recursive) to get S¹_n/2 and S²_n/2

Merge

For example

Algorithm mergesort (low, high) { // array A is global if low >= high then return // otherwise, divide mid = (low + high)/ 2 // recursively sort smaller array call mergesort (low, mid) call mergesort (mid + 1, high) // conquer // call merge (low, mid, high) }

Look in text for merge algorithm

if mid = high-low +1 time to merge - is O(n) - hence a cn term

let T(n) = time for mergesort

T(n) = a for n < 1 (for small sort)
2T(n/2)+ cn for n > 1 (cn for merge)

T(n) = 2 T (n/2) + cn
       = 2 (2T (n/4) + c(n/2)) + cn        equation n is n/2
       = 2² (T (n/2²)) + 2cn              algebra
       = 2² (2T (n/2³) + c(n/2²)) + 2cn        equation n is n/2²
       = 2³ T (n/2³) + 3cn                    algebra
...
       = 2^k T (n/2^k) + kcn

since 2^k=n, n/2^k = 1, and T(n/2^k) = a (remember T(1) = a), and k = log n we see

= an + cn log n is O(n log n)

Or you can try the technique of expanding with T(1), T(2), T(3)...to see the pattern.

Let's look at a trace of the recursive call:

D
I 4       7	2       5  	6       3	8       1
V 4       7	2       5  ||	6       3	8       1
I 4       7 ||	2       5  ||	6       3  ||	8       1
D 4  |    7  |	2  |    5   |	6  |    3   |	8   |   1
E 
-------------------------------------------------------------
C
O 4	  7  | 	2	5   |	3	6   |	1	8
N 
Q 2	  4	5	7  || 	1	3	6	8
U
E 1	  2	3	4	5	6	7	8
R

log n + 1 levels with 0(n) "merge" work at each level (8 comparisons at the top level, 4 comparisons for each of the 2 4's, 2 comparisons for each of the 4 2's)

so, "loop" log n times - then within each O(n) hence nlogn

Note: merging two arrays of size n/2 each, requires 2n memory locations (putting results into new array)

Can you do better possibly by investing more time

Ex: nonrecursive version of mergesort without using a stack.

Selection

Select k^th smallest element in the unsorted array A[1:n]

One solution: sort A; A (k) is answer

time: O(nlogn)

Can we make this better?
Yes, of course

We will do Selection by using a divide and conquer method which uses a partition of A.
(Partition (C.A.R.Hoare) used for selection and quicksort - breaking these two problems into another problem)

split into two - not sorted but all in one part smaller than all in other

A(i)< A(j) for all 1 < i < p
and p < j < n

If k < p then k^th element of A[1:n] = k^th element of A[1:p]
If k > p then k^th element of A[1:n] = (k-p)^th element of A[p+1:n]

6	3	4	1	8	5	2	7

6	3	4	1	5	2  |	8	7

<6 then > 6

another

3	5	1	7	2	6	4	8

3	1	2  |	5	7	6	4	8

<3 then > 3

T(n,k) = T(p,k) if k < p
T(n-p, k-p) o.w.

How to partition using extra array

O(n) time 2n memory locations

Partition in place

v ... ...

Left                 Right
Move ->          Move <-
until                 until
A(Left) > v       A(Right) < v

Interchange A(left) and A(right)

5 2 7 4 6 3 8 1

L, R?
this yields

5 2 1 4 6 3 8 7

again yields

5 2 1 4 3 6 8 7

stop when L > R

3 2 1 4 5 6 8 7

trade A[1] and A[p]

some pseudocode. To sort you would call partition again.

Algorithm Partition (l, u) { // A global // Partition A around v = A(l) // i.e. after rearranging, if A(p) = v then for all l <= i <= p // for all l <= i <= p A(i) <= v // and for all p < j <= u, A(j)>= v v = A(l) left = l right = u + 1 loop repeat left = left + 1 until (A(left) >= v) repeat right = right - 1 until (A(right) <= v) if left < right then interchange(A(left), A(right)) else exit forever Interchange (A(l), A(right)) }

Partition: O(n)

OK, so that is Partition. Now, for Select and Quicksort using partition (see text)

Some discussion on using Partition for Selection:
In the worst case partition may reduce a problem of size n by at most 1.

n-1

n-2

n steps of this

each checking 1+2+. . +n (really up to k steps but still O(n))

Hence, Select is O(n²) worse case. (worst case: sorted array)

However, the average is O(n) (proof in the text)

By choosing the partitioning element v more carefully we can get better time of O(n) even for the worse case. Pick v such that at most a fixed fraction of elements in A are < v
or a fixed fraction are > v

Median of medians

r - some constant

say n a multiple of r

Sort columns increasing top to bottom

Time to find median of 1 column

= r log r

. . . of n/r columns = O(n log r)

= O(n) since r is a constant

Rearrange columns: medians increase left to right

At most ¾ of elements < v

At most ¾ of elements > v

Hence a better choice of v to to the partition with.

NOTE: Book notes that this is true when the elements of the array are distinct. More work needs to be done if not (see page 171, 184 in edition 2)

Remember our original problem was to Select k^th smallest element in the unsorted array A[1:n]
Now with our better partition choice, let's look at the Selection algorithm:

	
Algorithm  Select (A, k, n)
{	 Divide A into n/r subsets each of size r. // (constant time)
	 M =  {m₁, m₂, . . , m_n/r} set of medians // (r elements in each of the n/r sets)
	 v =  Select(M, n/2r, n/r)
	                // median of medians "location " is 1/2*n/r = n/2r (1/2 of the set of medians)
	 Partition A around v   
	 Assume v is A (j)
	case
		: k = j :
			return (v)
		: k < j :
			return (Select(A [1:j-1], k, j-1))
		: k > j:
			return (Select(A [j+1:n], k-j, n-j-1))
	endcase
}

See text code for Figure 3.19 (follow link on index page - 3.18 pseudocode not there)

So, we have

Find the medians: O(n) time (remember r log r * n/r is O(n log r) = O(n) since r is a constant)

Find the pivot: Recursive call to find median of medians = T(n/r)

Partition: O(n) time

Recursive call on smaller problem < T (¾ n)

Suppose r = 5

T(n) < T(n/5) + T(3n/4) + cn

this is T(n) < cn for n < 24 with c chosen sufficiently large

OR, T(n) < 20cn for n > 1. Proof by induction (book says "easily establishes this")

Note: Here we see the use of "divide and conquer" interpreted in two ways. Rather than just "brute force" solving the problem, a completely different side journey is taken that improves the performance. Hence we are not only dividing the instance of the problem, we are also dividing the problem. Nice, I like that.
Oops, in the lecture at this point I said Quicksort was O(n) - we just did Select, not Quicksort. Sorry. Quicksort is still O(nlogn) BUT it is still faster (empirically) than mergesort. (page 161)