Courses

# Divide and Conquer Notes | EduRev

## : Divide and Conquer Notes | EduRev

``` Page 1

Divide-and-Conquer
"Divide et impera"
"Veni, vidi, vici"
- Julius Caesar
100BC - 44BC
2
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
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 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
¦ 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
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 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
¦ 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
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 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
¦ 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
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 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
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
¦ 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
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 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
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
21
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!