Page 1 Divide-and-Conquer "Divide et impera" "Veni, vidi, vici" - Julius Caesar 100BC - 44BC 2 Divide-and-Conquer Most 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: N 2 . ¦ 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. 3 Why Does It Matter? 1000 Time to solve a problem of size 10,000 100,000 million 10 million 1.3 seconds 22 minutes 15 days 41 years 41 millennia 920 3,600 14,000 41,000 1,000 Run time (nanoseconds) 1.3 N 3 second Max size problem solved in one minute hour day 10 msec 1 second 1.7 minutes 2.8 hours 1.7 weeks 10,000 77,000 600,000 2.9 million 100 10 N 2 0.4 msec 6 msec 78 msec 0.94 seconds 11 seconds 1 million 49 million 2.4 trillion 50 trillion 10+ 47 N log 2 N 0.048 msec 0.48 msec 4.8 msec 48 msec 0.48 seconds 21 million 1.3 billion 76 trillion 1,800 trillion 10 48 N N multiplied by 10, time multiplied by 4 Orders of Magnitude 10 -10 Meters Per Second 10 -8 10 -6 10 -4 10 -2 1 10 2 1.2 in / decade Imperial Units 1 ft / year 3.4 in / day 1.2 ft / hour 2 ft / minute 2.2 mi / hour 220 mi / hour Continental drift Example Hair growing Glacier Gastro-intestinal tract Ant Human walk Propeller airplane 10 4 10 6 10 8 370 mi / min 620 mi / sec 62,000 mi / sec Space shuttle Earth in galactic orbit 1/3 speed of light 1 Seconds 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 1 second Equivalent 1.7 minutes 17 minutes 2.8 hours 1.1 days 1.6 weeks 3.8 months 3.1 years 3.1 decades 3.1 centuries forever 10 21 age of universe 2 10 thousand 2 20 million 2 30 billion . . . 10 10 seconds Powers of 2 Page 2 Divide-and-Conquer "Divide et impera" "Veni, vidi, vici" - Julius Caesar 100BC - 44BC 2 Divide-and-Conquer Most 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: N 2 . ¦ 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. 3 Why Does It Matter? 1000 Time to solve a problem of size 10,000 100,000 million 10 million 1.3 seconds 22 minutes 15 days 41 years 41 millennia 920 3,600 14,000 41,000 1,000 Run time (nanoseconds) 1.3 N 3 second Max size problem solved in one minute hour day 10 msec 1 second 1.7 minutes 2.8 hours 1.7 weeks 10,000 77,000 600,000 2.9 million 100 10 N 2 0.4 msec 6 msec 78 msec 0.94 seconds 11 seconds 1 million 49 million 2.4 trillion 50 trillion 10+ 47 N log 2 N 0.048 msec 0.48 msec 4.8 msec 48 msec 0.48 seconds 21 million 1.3 billion 76 trillion 1,800 trillion 10 48 N N multiplied by 10, time multiplied by 4 Orders of Magnitude 10 -10 Meters Per Second 10 -8 10 -6 10 -4 10 -2 1 10 2 1.2 in / decade Imperial Units 1 ft / year 3.4 in / day 1.2 ft / hour 2 ft / minute 2.2 mi / hour 220 mi / hour Continental drift Example Hair growing Glacier Gastro-intestinal tract Ant Human walk Propeller airplane 10 4 10 6 10 8 370 mi / min 620 mi / sec 62,000 mi / sec Space shuttle Earth in galactic orbit 1/3 speed of light 1 Seconds 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 1 second Equivalent 1.7 minutes 17 minutes 2.8 hours 1.1 days 1.6 weeks 3.8 months 3.1 years 3.1 decades 3.1 centuries forever 10 21 age of universe 2 10 thousand 2 20 million 2 30 billion . . . 10 10 seconds Powers of 2 5 A Useful Recurrence Relation T(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 log 2 N). ¦ Equivalently, O(log b N) for any b > 1. Øø () ºß () + + £ £ otherwise ) ( 2 / 2 / if ) 1 ( ) T( combine half right solve half left solve 0 3 2 1 43 42 1 43 42 1 N O N T N T n N O N 6 Analysis of Recurrence: Recursion Tree Assuming 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) cN T(N / 2 k ) 2(cN/2) 4(cN/4) 2 k (cN / 2 k ) N/2 (2c) . . . . . . + = = otherwise ) 2 / ( 2 1 if 0 ) T( cN N T N N log 2 N cN log 2 N 7 Analysis of Recurrence Proof by induction on N. ¦ Base case: N = 1. ¦ Define n 1 = º n / 2ß , n 2 = Ø n / 2ø . ¦ Induction step: assume true for 1, 2, . . . , N –1. Øø () ºß () { Øø N cN N T cN N T N T N N 2 combine half right solve half left solve log ) ( otherwise 2 / 2 / 1 if 0 ) T( £ + + = £ 43 42 1 43 42 1 Øø Ø ø Øø Øø Øø Øø Øø n cn cn n cn cn n cn cn n cn n cn cn n cn n cn cn n T n T N T 2 2 2 2 2 2 2 2 2 1 2 2 2 1 2 1 2 1 log ) 1 log ( log log log log log ) ( ) ( ) ( = + - £ + = + + £ + + £ + + £ Øø Øø Øø Øø 1 log log 2 / 2 2 / 2 2 2 log 2 2 - £ £ = n n n n n 8 Counting Inversions Web 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 = { a 1 , a 2 , . . . , a N }. ¦ Number of inversions between two preference lists. ¦ Songs i and j inverted if i < j, but a i > a j You 1 4 3 2 5 Me 1 3 2 4 5 A B C D E Songs 3 2 Inversion Inversions {3, 2}, {4, 2} Page 3 Divide-and-Conquer "Divide et impera" "Veni, vidi, vici" - Julius Caesar 100BC - 44BC 2 Divide-and-Conquer Most 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: N 2 . ¦ 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. 3 Why Does It Matter? 1000 Time to solve a problem of size 10,000 100,000 million 10 million 1.3 seconds 22 minutes 15 days 41 years 41 millennia 920 3,600 14,000 41,000 1,000 Run time (nanoseconds) 1.3 N 3 second Max size problem solved in one minute hour day 10 msec 1 second 1.7 minutes 2.8 hours 1.7 weeks 10,000 77,000 600,000 2.9 million 100 10 N 2 0.4 msec 6 msec 78 msec 0.94 seconds 11 seconds 1 million 49 million 2.4 trillion 50 trillion 10+ 47 N log 2 N 0.048 msec 0.48 msec 4.8 msec 48 msec 0.48 seconds 21 million 1.3 billion 76 trillion 1,800 trillion 10 48 N N multiplied by 10, time multiplied by 4 Orders of Magnitude 10 -10 Meters Per Second 10 -8 10 -6 10 -4 10 -2 1 10 2 1.2 in / decade Imperial Units 1 ft / year 3.4 in / day 1.2 ft / hour 2 ft / minute 2.2 mi / hour 220 mi / hour Continental drift Example Hair growing Glacier Gastro-intestinal tract Ant Human walk Propeller airplane 10 4 10 6 10 8 370 mi / min 620 mi / sec 62,000 mi / sec Space shuttle Earth in galactic orbit 1/3 speed of light 1 Seconds 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 1 second Equivalent 1.7 minutes 17 minutes 2.8 hours 1.1 days 1.6 weeks 3.8 months 3.1 years 3.1 decades 3.1 centuries forever 10 21 age of universe 2 10 thousand 2 20 million 2 30 billion . . . 10 10 seconds Powers of 2 5 A Useful Recurrence Relation T(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 log 2 N). ¦ Equivalently, O(log b N) for any b > 1. Øø () ºß () + + £ £ otherwise ) ( 2 / 2 / if ) 1 ( ) T( combine half right solve half left solve 0 3 2 1 43 42 1 43 42 1 N O N T N T n N O N 6 Analysis of Recurrence: Recursion Tree Assuming 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) cN T(N / 2 k ) 2(cN/2) 4(cN/4) 2 k (cN / 2 k ) N/2 (2c) . . . . . . + = = otherwise ) 2 / ( 2 1 if 0 ) T( cN N T N N log 2 N cN log 2 N 7 Analysis of Recurrence Proof by induction on N. ¦ Base case: N = 1. ¦ Define n 1 = º n / 2ß , n 2 = Ø n / 2ø . ¦ Induction step: assume true for 1, 2, . . . , N –1. Øø () ºß () { Øø N cN N T cN N T N T N N 2 combine half right solve half left solve log ) ( otherwise 2 / 2 / 1 if 0 ) T( £ + + = £ 43 42 1 43 42 1 Øø Ø ø Øø Øø Øø Øø Øø n cn cn n cn cn n cn cn n cn n cn cn n cn n cn cn n T n T N T 2 2 2 2 2 2 2 2 2 1 2 2 2 1 2 1 2 1 log ) 1 log ( log log log log log ) ( ) ( ) ( = + - £ + = + + £ + + £ + + £ Øø Øø Øø Øø 1 log log 2 / 2 2 / 2 2 2 log 2 2 - £ £ = n n n n n 8 Counting Inversions Web 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 = { a 1 , a 2 , . . . , a N }. ¦ Number of inversions between two preference lists. ¦ Songs i and j inverted if i < j, but a i > a j You 1 4 3 2 5 Me 1 3 2 4 5 A B C D E Songs 3 2 Inversion Inversions {3, 2}, {4, 2} 9 Counting Inversions Brute-force solution. ¦ Check all pairs i and j such that i < j. ¦ Q (N 2 ) comparisons. Note: there can be a quadratic number of inversions. ¦ Asymptotically faster algorithm must compute total number without even looking at each inversion individually. 10 Counting Inversions: Divide-and-Conquer Divide-and-conquer. 4 8 10 2 1 5 12 11 3 7 6 9 11 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 O(1) 12 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. ¦ Conquer: recursively count inversions in each half separately. 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 5 blue-blue inversions 8 green-green inversions 2T(N / 2) O(1) Page 4 Divide-and-Conquer "Divide et impera" "Veni, vidi, vici" - Julius Caesar 100BC - 44BC 2 Divide-and-Conquer Most 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: N 2 . ¦ 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. 3 Why Does It Matter? 1000 Time to solve a problem of size 10,000 100,000 million 10 million 1.3 seconds 22 minutes 15 days 41 years 41 millennia 920 3,600 14,000 41,000 1,000 Run time (nanoseconds) 1.3 N 3 second Max size problem solved in one minute hour day 10 msec 1 second 1.7 minutes 2.8 hours 1.7 weeks 10,000 77,000 600,000 2.9 million 100 10 N 2 0.4 msec 6 msec 78 msec 0.94 seconds 11 seconds 1 million 49 million 2.4 trillion 50 trillion 10+ 47 N log 2 N 0.048 msec 0.48 msec 4.8 msec 48 msec 0.48 seconds 21 million 1.3 billion 76 trillion 1,800 trillion 10 48 N N multiplied by 10, time multiplied by 4 Orders of Magnitude 10 -10 Meters Per Second 10 -8 10 -6 10 -4 10 -2 1 10 2 1.2 in / decade Imperial Units 1 ft / year 3.4 in / day 1.2 ft / hour 2 ft / minute 2.2 mi / hour 220 mi / hour Continental drift Example Hair growing Glacier Gastro-intestinal tract Ant Human walk Propeller airplane 10 4 10 6 10 8 370 mi / min 620 mi / sec 62,000 mi / sec Space shuttle Earth in galactic orbit 1/3 speed of light 1 Seconds 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 1 second Equivalent 1.7 minutes 17 minutes 2.8 hours 1.1 days 1.6 weeks 3.8 months 3.1 years 3.1 decades 3.1 centuries forever 10 21 age of universe 2 10 thousand 2 20 million 2 30 billion . . . 10 10 seconds Powers of 2 5 A Useful Recurrence Relation T(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 log 2 N). ¦ Equivalently, O(log b N) for any b > 1. Øø () ºß () + + £ £ otherwise ) ( 2 / 2 / if ) 1 ( ) T( combine half right solve half left solve 0 3 2 1 43 42 1 43 42 1 N O N T N T n N O N 6 Analysis of Recurrence: Recursion Tree Assuming 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) cN T(N / 2 k ) 2(cN/2) 4(cN/4) 2 k (cN / 2 k ) N/2 (2c) . . . . . . + = = otherwise ) 2 / ( 2 1 if 0 ) T( cN N T N N log 2 N cN log 2 N 7 Analysis of Recurrence Proof by induction on N. ¦ Base case: N = 1. ¦ Define n 1 = º n / 2ß , n 2 = Ø n / 2ø . ¦ Induction step: assume true for 1, 2, . . . , N –1. Øø () ºß () { Øø N cN N T cN N T N T N N 2 combine half right solve half left solve log ) ( otherwise 2 / 2 / 1 if 0 ) T( £ + + = £ 43 42 1 43 42 1 Øø Ø ø Øø Øø Øø Øø Øø n cn cn n cn cn n cn cn n cn n cn cn n cn n cn cn n T n T N T 2 2 2 2 2 2 2 2 2 1 2 2 2 1 2 1 2 1 log ) 1 log ( log log log log log ) ( ) ( ) ( = + - £ + = + + £ + + £ + + £ Øø Øø Øø Øø 1 log log 2 / 2 2 / 2 2 2 log 2 2 - £ £ = n n n n n 8 Counting Inversions Web 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 = { a 1 , a 2 , . . . , a N }. ¦ Number of inversions between two preference lists. ¦ Songs i and j inverted if i < j, but a i > a j You 1 4 3 2 5 Me 1 3 2 4 5 A B C D E Songs 3 2 Inversion Inversions {3, 2}, {4, 2} 9 Counting Inversions Brute-force solution. ¦ Check all pairs i and j such that i < j. ¦ Q (N 2 ) comparisons. Note: there can be a quadratic number of inversions. ¦ Asymptotically faster algorithm must compute total number without even looking at each inversion individually. 10 Counting Inversions: Divide-and-Conquer Divide-and-conquer. 4 8 10 2 1 5 12 11 3 7 6 9 11 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 O(1) 12 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. ¦ Conquer: recursively count inversions in each half separately. 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 5 blue-blue inversions 8 green-green inversions 2T(N / 2) O(1) 13 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. ¦ Conquer: recursively count inversions in each half. ¦ Combine: count inversions where a i and a j are in different halves. 5 blue-blue inversions 8 green-green inversions 9 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(N 2 ) 14 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. ¦ Conquer: recursively count inversions in each half. ¦ Combine: count inversions where a i and a j are 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 inversions O(1) 2T(N / 2) O(N 2 ) Total = 5 + 8 + 9 = 22. O(1) 15 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. ¦ Conquer: recursively count inversions in each half. ¦ Combine: count inversions where a i and a j are 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 inversions Can we do this step in sub-quadratic time? O(1) 2T(N / 2) O(1) 16 4 8 10 2 1 5 12 11 3 7 6 9 4 5 8 10 1 2 7 9 11 12 3 6 9 blue-green inversions: 4 + 2 + 2 + 1 + 0 + 0 Counting Inversions: Good Combine Combine: count inversions where a i and a j are 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( 2 N N O N N N O N T N T N = + + = Page 5 Divide-and-Conquer "Divide et impera" "Veni, vidi, vici" - Julius Caesar 100BC - 44BC 2 Divide-and-Conquer Most 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: N 2 . ¦ 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. 3 Why Does It Matter? 1000 Time to solve a problem of size 10,000 100,000 million 10 million 1.3 seconds 22 minutes 15 days 41 years 41 millennia 920 3,600 14,000 41,000 1,000 Run time (nanoseconds) 1.3 N 3 second Max size problem solved in one minute hour day 10 msec 1 second 1.7 minutes 2.8 hours 1.7 weeks 10,000 77,000 600,000 2.9 million 100 10 N 2 0.4 msec 6 msec 78 msec 0.94 seconds 11 seconds 1 million 49 million 2.4 trillion 50 trillion 10+ 47 N log 2 N 0.048 msec 0.48 msec 4.8 msec 48 msec 0.48 seconds 21 million 1.3 billion 76 trillion 1,800 trillion 10 48 N N multiplied by 10, time multiplied by 4 Orders of Magnitude 10 -10 Meters Per Second 10 -8 10 -6 10 -4 10 -2 1 10 2 1.2 in / decade Imperial Units 1 ft / year 3.4 in / day 1.2 ft / hour 2 ft / minute 2.2 mi / hour 220 mi / hour Continental drift Example Hair growing Glacier Gastro-intestinal tract Ant Human walk Propeller airplane 10 4 10 6 10 8 370 mi / min 620 mi / sec 62,000 mi / sec Space shuttle Earth in galactic orbit 1/3 speed of light 1 Seconds 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 1 second Equivalent 1.7 minutes 17 minutes 2.8 hours 1.1 days 1.6 weeks 3.8 months 3.1 years 3.1 decades 3.1 centuries forever 10 21 age of universe 2 10 thousand 2 20 million 2 30 billion . . . 10 10 seconds Powers of 2 5 A Useful Recurrence Relation T(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 log 2 N). ¦ Equivalently, O(log b N) for any b > 1. Øø () ºß () + + £ £ otherwise ) ( 2 / 2 / if ) 1 ( ) T( combine half right solve half left solve 0 3 2 1 43 42 1 43 42 1 N O N T N T n N O N 6 Analysis of Recurrence: Recursion Tree Assuming 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) cN T(N / 2 k ) 2(cN/2) 4(cN/4) 2 k (cN / 2 k ) N/2 (2c) . . . . . . + = = otherwise ) 2 / ( 2 1 if 0 ) T( cN N T N N log 2 N cN log 2 N 7 Analysis of Recurrence Proof by induction on N. ¦ Base case: N = 1. ¦ Define n 1 = º n / 2ß , n 2 = Ø n / 2ø . ¦ Induction step: assume true for 1, 2, . . . , N –1. Øø () ºß () { Øø N cN N T cN N T N T N N 2 combine half right solve half left solve log ) ( otherwise 2 / 2 / 1 if 0 ) T( £ + + = £ 43 42 1 43 42 1 Øø Ø ø Øø Øø Øø Øø Øø n cn cn n cn cn n cn cn n cn n cn cn n cn n cn cn n T n T N T 2 2 2 2 2 2 2 2 2 1 2 2 2 1 2 1 2 1 log ) 1 log ( log log log log log ) ( ) ( ) ( = + - £ + = + + £ + + £ + + £ Øø Øø Øø Øø 1 log log 2 / 2 2 / 2 2 2 log 2 2 - £ £ = n n n n n 8 Counting Inversions Web 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 = { a 1 , a 2 , . . . , a N }. ¦ Number of inversions between two preference lists. ¦ Songs i and j inverted if i < j, but a i > a j You 1 4 3 2 5 Me 1 3 2 4 5 A B C D E Songs 3 2 Inversion Inversions {3, 2}, {4, 2} 9 Counting Inversions Brute-force solution. ¦ Check all pairs i and j such that i < j. ¦ Q (N 2 ) comparisons. Note: there can be a quadratic number of inversions. ¦ Asymptotically faster algorithm must compute total number without even looking at each inversion individually. 10 Counting Inversions: Divide-and-Conquer Divide-and-conquer. 4 8 10 2 1 5 12 11 3 7 6 9 11 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 O(1) 12 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. ¦ Conquer: recursively count inversions in each half separately. 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 5 blue-blue inversions 8 green-green inversions 2T(N / 2) O(1) 13 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. ¦ Conquer: recursively count inversions in each half. ¦ Combine: count inversions where a i and a j are in different halves. 5 blue-blue inversions 8 green-green inversions 9 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(N 2 ) 14 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. ¦ Conquer: recursively count inversions in each half. ¦ Combine: count inversions where a i and a j are 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 inversions O(1) 2T(N / 2) O(N 2 ) Total = 5 + 8 + 9 = 22. O(1) 15 4 8 10 2 1 5 12 11 3 7 6 9 4 8 10 2 1 5 12 11 3 7 6 9 Counting Inversions: Divide-and-Conquer Divide-and-conquer. ¦ Divide: separate list into two pieces. ¦ Conquer: recursively count inversions in each half. ¦ Combine: count inversions where a i and a j are 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 inversions Can we do this step in sub-quadratic time? O(1) 2T(N / 2) O(1) 16 4 8 10 2 1 5 12 11 3 7 6 9 4 5 8 10 1 2 7 9 11 12 3 6 9 blue-green inversions: 4 + 2 + 2 + 1 + 0 + 0 Counting Inversions: Good Combine Combine: count inversions where a i and a j are 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( 2 N N O N N N O N T N T N = + + = 17 13 blue-green inversions: 6 + 3 + 2 + 2 + 0 + 0 Counting Inversions: Better Combine Combine: count inversions where a i and a j are 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 / ) ( N N O N N O N T N T N T = + + = 10 14 18 19 3 7 16 17 23 25 2 11 7 10 11 14 2 3 18 19 23 25 16 17 18 Closest Pair Given N points in the plane, find a pair that is closest together. ¦ For concreteness, we assume Euclidean distances. ¦ Foundation of then-fledgling field of computational geometry. ¦ Graphics, computer vision, geographic information systems, molecular modeling, air traffic control. Brute force solution. ¦ Check all pairs of points p and q. ¦ Q (N 2 ) comparisons. One dimensional version (points on a line). ¦ O(N log N) easy. Assumption to make presentation cleaner. ¦ No two points have same x coordinate. 19 Closest Pair Algorithm. ¦ Divide: draw vertical line so that roughly N / 2 points on each side. 20 Closest Pair Algorithm. ¦ Divide: draw vertical line so that roughly N / 2 points on each side. ¦ Conquer: find closest pair in each side recursively. 12 21Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!