Divide-and-Conquer"Divide et impera""Veni, vidi, vici"-Julius Caesar100BC - 44BC2Divide-and-ConquerMost widespread application of divide-and-conquer.■ Break up problem into two pieces of equal size.■ Solve two sub-problems independently by recursion.■ Combine two results in overall solution in linear time.Consequence.■ Brute force / naïve solution: N2.■ Divide-and-conquer: N log N.Familiar example.■ Mergesort.This course.■ Counting inversions, closest pair of points, order statistics, fast matrix multiplication, fast integer multiplication, FFT.3Why Does It Matter?1000Time tosolve aproblemof size10,000100,000million10 million1.3 seconds22 minutes15 days41 years41 millennia9203,60014,00041,0001,000Run time(nanoseconds)1.3 N3secondMax sizeproblemsolvedin oneminutehourday10 msec1 second1.7 minutes2.8 hours1.7 weeks10,00077,000600,0002.9 million10010 N20.4 msec6 msec78 msec0.94 seconds11 seconds1 million49 million2.4 trillion50 trillion10+47 N log2N0.048 msec0.48 msec4.8 msec48 msec0.48 seconds21 million1.3 billion76 trillion1,800 trillion1048 NN multiplied by 10,time multiplied by4Orders of Magnitude10-10Meters PerSecond10-810-610-410-211021.2 in / decadeImperialUnits1 ft / year3.4 in / day1.2 ft / hour2 ft / minute2.2 mi / hour220 mi / hourContinental driftExampleHair growingGlacierGastro-intestinal tractAntHuman walkPropeller airplane104106108370 mi / min620 mi / sec62,000 mi / secSpace shuttleEarth in galactic orbit1/3 speed of light1Seconds10210310410510610710810910101 secondEquivalent1.7 minutes17 minutes2.8 hours1.1 days1.6 weeks3.8 months3.1 years3.1 decades3.1 centuriesforever1021age ofuniverse210thousand220million230billion. . .10 10 secondsPowersof 25A Useful Recurrence RelationT(N) = worst case running time on input of size N.■ Note: O(1) is "standard" abuse of notation.Alternate informal form: T(N) ≤ T(N/2) + O(N).■ Implicitly assumes N is a power of 2.■ Implicitly assume T(N) ∈ O(1) for sufficiently small N.Solution.■ Any function satisfying above recurrence is ∈ O(N log2N). ■ Equivalently, O(logbN) for any b > 1.()()++≤≤otherwise)(2/2/ if)1()T(combinehalfright solvehalfleft solve03214342143421NONTNTnNON6Analysis of Recurrence: Recursion TreeAssuming N is a power of 2.T(N)T(N/2)T(N/2)T(N/4)T(N/4)T(N/4) T(N/4)T(2) T(2)T(2) T(2) T(2) T(2) T(2) T(2)cNT(N / 2k)2(cN/2)4(cN/4)2k (cN / 2k)N/2 (2c). . .. . .+==otherwise)2/(21 if0)T(cNNTNNlog2NcN log2N7Analysis of RecurrenceProof by induction on N.■ Base case: N = 1.■ Define n1= n / 2 , n2= n / 2.■ Induction step: assume true for 1, 2, . . . , N –1.()(){NcNNTcNNTNTNN2combinehalfright solvehalfleft solvelog)(otherwise2/2/1 if0)T(≤⇒++=≤4342143421ncncnncncnncncnncnncncnncnncncnnTnTNT222222222122212121log)1log(logloglogloglog)()()(=+−≤+=++≤++≤++≤1loglog2/22/222log22−≤⇒≤=nnnnn8Counting InversionsWeb site tries to match your preferences with others on Internet.■ You rank N songs.■ Web site consults database to find people with similar rankings.Closeness metric.■ My rank = { 1, 2, . . . , N }.■ Your rank = { a1, a2, . . . , aN }.■ Number of inversions between two preference lists.■ Songs i and j inverted if i < j, but ai> ajYou 1 43 2 5Me 1 32 4 5A B C D ESongs3 2InversionInversions{3, 2}, {4, 2}9Counting InversionsBrute-force solution.■ Check all pairs i and j such that i < j.■ Θ (N2) comparisons.Note: there can be a quadratic number of inversions.■ Asymptotically faster algorithm must compute total number without even looking at each inversion individually.10Counting Inversions: Divide-and-ConquerDivide-and-conquer.4 8 10 21 5 12 11 3 76 911Counting Inversions: Divide-and-ConquerDivide-and-conquer.■ Divide: separate list into two pieces.4 8 10 21 5 12 11 3 76 94 8 10 21 5 12 11 3 76 9O(1)12Counting Inversions: Divide-and-ConquerDivide-and-conquer.■ Divide: separate list into two pieces.■ Conquer: recursively count inversions in each half separately.4 8 10 21 5 12 11 3 76 94 8 10 21 5 12 11 3 76 95 blue-blue inversions 8 green-green inversions2T(N / 2)O(1)134 8 10 21 5 12 11 3 76 94 8 10 21 5 12 11 3 76 9Counting Inversions: Divide-and-ConquerDivide-and-conquer.■ Divide: separate list into two pieces.■ Conquer: recursively count inversions in each half.■ Combine: count inversions where aiand ajare in different halves.5 blue-blue inversions 8 green-green inversions9 blue-green inversions:{5-3, 4-3, 8-6, 8-3, 8-7, 10-6, 10-9, 10-3, 10-7} O(1)2T(N / 2)O(N2)144 8 10 21 5 12 11 3 76 94 8 10 21 5 12 11 3 76 9Counting Inversions: Divide-and-ConquerDivide-and-conquer.■ Divide: separate list into two pieces.■ Conquer: recursively count inversions in each half.■ Combine: count inversions where aiand ajare in different halves.■ Return sum of three quantities.9 blue-green inversions:{5-3, 4-3, 8-6, 8-3, 8-7, 10-6, 10-9, 10-3, 10-7} 5 blue-blue inversions 8 green-green inversionsO(1)2T(N / 2)O(N2)Total = 5 + 8 + 9 = 22.O(1)154 8 10 21 5 12 11 3 76 94 8 10 21 5 12 11 3 76 9Counting Inversions: Divide-and-ConquerDivide-and-conquer.■ Divide: separate list into two pieces.■ Conquer: recursively count inversions in each half.■ Combine: count inversions where aiand ajare in different halves.■ Return sum of three quantities.9 blue-green inversions:{5-3, 4-3, 8-6, 8-3, 8-7, 10-6, 10-9, 10-3, 10-7} Total = 5 + 8 + 9 = 22.5 blue-blue inversions 8 green-green inversionsCan we do this step in sub-quadratic time?O(1)2T(N / 2)O(1)164 8 10 21 5 1211 3 76 94 5 8 101 2 7 9 11 123 69 blue-green inversions: 4 + 2 + 2 + 1 + 0 + 0Counting Inversions: Good CombineCombine: count inversions where aiand ajare in different halves.■ Key idea: easy if each half is sorted.■ Sort each half.■ Count inversions.O(N log N)O(N)()())log()T()log(2/2/)T(2NNONNNONTNTN=⇒++=1713 blue-green inversions: 6 + 3 + 2 + 2 + 0 + 0 Counting Inversions: Better CombineCombine: count inversions where aiand ajare in different halves.■ Assume each half is pre-sorted.■ Count inversions.■ Merge two sorted halves into sorted whole.O(N)O(N)()())log()T()(2/2/)(NNONNONTNTNT=⇒++=10 14 18 193 7 16 17 23 252 117 10 11 142 3 18 19 23 2516 1718Closest PairGiven N points in the plane, find a pair that is closest together.■ For concreteness, we assume Euclidean distances.■