Advanced Algorithm Analysis: Muhammad Nadeem July 15, 2017

Advanced Algorithm Analysis
Muhammad Nadeem
July 15, 2017

Analysis of Merge Sort
Running me T(n) of Merge Sort:
Divide: compu ng the middle takes (1)
Conquer: solving 2 subproblems takes 2T(n/2)
Combine: merging n elements takes (n)
Total:
T(n) = (1) if n = 1
T(n) = 2T(n/2) + (n) if n > 1
How do we find a closed-form solu on of this
recurrence equa on?
Recurrence Rela ons
Equa on or an inequality that characterizes a
func on by its values on smaller inputs.
Recurrence rela ons arise when we analyze the
running me of itera ve or recursive algorithms.
Ex: Divide and Conquer.
T(n) = (1) if n c
T(n) = a T(n/b) + D(n) + C(n) otherwise
Solu on Methods (Chapter 4)
Subs tu on Method.
Recursion-tree Method.
Master Method.
Subs tu on Method
Guess the form of the solu on, then
use mathema cal induc on to show it correct.
Subs tute guessed answer for the func on when the
induc ve hypothesis is applied to smaller values
hence, the name.
Works well when the solu on is easy to guess.
No general way to guess the correct solu on.
Example
Recurrence: T(n) = 1 if n = 1
T(n) = 2T(n/2) + n if n > 1
Guess: T(n) = n lg n + n.
Induc on:
Basis: n = 1 n lg n + n = 1 = T(n).
Hypothesis: T(k) = k lg k + k for all k < n.
Induc ve Step: T(n) = 2 T(n/2) + n
= 2 ((n/2)lg(n/2) + (n/2)) + n
= n (lg(n/2)) + 2n
= n lg n n + 2n
= n lg n + n
Exercise
Recurrence: T(n) = 1 if n = 1
T(n) = T(n/2) + 1 if n > 1
Note that this is the recurrence for binary search.
Guess: T(n) = lg n + 1.
Induc on:
Basis: n = 1 lg n + 1 = 1 = T(n).
Hypothesis: T(k) = lg k + 1 for all k < n.
Induc ve Step: T(n) = T(n/2) + 1
=
Recursion-tree Method
Making a good guess is some mes difficult with
the subs tu on method.
Use recursion trees to devise good guesses.
Recursion Trees
Show successive expansions of recurrences using
trees.
Keep track of the me spent on the subproblems of
a divide and conquer algorithm.
Help organize the algebraic bookkeeping necessary
to solve a recurrence.
Recursion Tree Example
Running me of Merge Sort:
T(n) = (1) if n = 1
T(n) = 2T(n/2) + (n) if n > 1
Rewrite the recurrence as
T(n) = c if n = 1
T(n) = 2T(n/2) + cn if n > 1
c > 0: Running me for the base case and
me per array element for the divide and
combine steps.
Recursion Tree for Merge Sort
For the original problem, we have Each of the size n/2 problems has a cost
a cost of cn, plus two of cn/2 plus two subproblems, each
subproblems each of size (n/2) cos ng T(n/4).
and running me T(n/2).
cn
cn
Cost of divide and
merge.
cn/ 2 cn/ 2
T(n/ 2) T(n/ 2)
T(n/ 4) T(n/ 4) T(n/ 4) T(n/ 4)
Cost of sor ng
subproblems.
Con nue expanding un l the problem size reduces to 1.
cn cn
cn/ 2 cn/ 2 cn
lg n
cn/ 4 cn/ 4 cn/ 4 cn/ 4 cn
c c c c c c cn
Total : cnlgn+cn
Con nue expanding un l the problem size reduces to 1.
cn
Each level has total cost cn.
Each me we go down one level, the number
of subproblems doubles, but the cost per
subproblem halves cost per level remains
cn/ 2 cn/ 2 the same.
There are lg n + 1 levels, height is lg n.
(Assuming n is a power of 2.)
Total cost = sum of costs at each level =
(lg n + 1)cn = cnlgn + cn = (n lgn).
cn/ 4 cn/ 4 cn/ 4 cn/ 4
c c c c c c
Recursion Tree Another Example
T (n) T (n /3) T (2n /3) n
The Master Method
Based on the Master theorem.
approach for solving recurrences of
the form
T(n) = aT(n/b) + f(n)
a 1, b > 1 are constants.
f(n) is asympto cally posi ve.
Requires memoriza on of three cases.
Master Method
Let and b>1 be constants, let f(n) be any
func on, and let T(n) be defined by the recurrence
T (n) aT (n / b) f (n)
The Master Theorem gives solu ons for the
following three cases:
1. If f (n) is O(n logb a ) for some constant 0,
then T (n) is (n logb a ).
logb a logb a
2. If f (n) is (n ), then T (n) is (n lg n).
logb a
3. If f (n) is (n ) for some constant 0, and if
af (n / b) cf (n) for some c 1, then T (n) is ( f (n)).
Simplified Master Method
Master Method Intui on
Three common cases:
1) Running me dominated by cost at leaves
2) Running me dominated by cost at root
3) Running me evenly distributed throughout the tree
Consequently, to solve the recurrence, we need
only to characterize the dominant term
In each case compare f (n) with O(nlog a )
b
The master method cannot be used to solve

every recurrence; there is a gap between cases 1
and 2, as well as cases 2 and 3
Strategy
Extract a, b, and f(n) from a given recurrence
logb a
Determine n
logb a
Compare f(n) and n asympto cally
Determine appropriate MT case, and apply
Example merge sort
T ( n) 2T ( n / 2) ( n)
a 2, b 2; n logb a n log2 2 n (n)
Also f (n) ( n)
Case 2: T (n) n logb a lg n n lg n
Examples
Binary-search(A, p, r, s):
T ( n) T ( n / 2) 1 q (p+r)/2
a 1, b 2; n log 2 1 1 if A[q]=s then return q
else if A[q]>s then
also f ( n) 1, f ( n) (1)
Binary-search(A, p, q-1, s)
Case 2: T ( n) (lg n) else Binary-search(A, q+1, r, s)
T ( n) 9T (n / 3) n
a 9, b 3;
f ( n) n, f (n) O (n log3 9 ) with 1
Case 1: T ( n) n2
Examples (2)
T (n) 3T (n / 4) n lg n
a 3, b 4; n log4 3 n 0.793
f ( n) n lg n, f ( n) ( n log4 3 ) with 0.2
Case 3:
Regularity condition
af (n / b) 3(n / 4) lg(n / 4) (3 / 4) n lg n cf (n) for c 3 / 4
T ( n) (n lg n)
T ( n) 2T (n / 2) n lg n
a 2, b 2; n log2 2 n1
f ( n) n lg n, f (n) (n1 ) with ?
also n lg n / n1 lg n
neither Case 3 nor Case 2!
Examples (3)
T ( n) 4T (n / 2) n3
a 4, b 2; nlog2 4 n2
f ( n) n3 ; f ( n) (n2 )
Case 3: T (n) n3
Checking the regularity condition
4 f (n / 2) cf (n)
4n3 / 8 cn3
n3 / 2 cn3
c 3/ 4 1
Common recurrences
It helps to remember the solu ons of common
and simple recurrences, especially those that are
associated with well-known algorithms
T(n) = T(n/2) + 1 T(n) is O(log n)
T(n) = 2T(n/2) + 1 T(n) is O(n)
T(n) = 2T(n/2) + n T(n) is O(n log n)
T(n) = 3T(n/2) + n T(n) is O(nlog23)
T(n) = 4T(n/2) + n T(n) is O(n2)
T(n) = T(n-1) + n T(n) is O(n2)
T(n) = 2T(n-1) + 1 T(n) is O(2n)
Summary of Sor ng Algorithms
Algorithm Time Notes
slow
selection-sort O(n2) in-place
for small data sets (< 1K)
slow
insertion-sort O(n2) in-place
for small data sets (< 1K)
fast
stable but not in-place
merge-sort O(n log n) sequential data access
for huge data sets (> 1M)
External sor ng
What if the data to be sorted does not fit in RAM?
Must read from and write to disk files during sor ng.
For external-memory algorithms, the objec ve is to
minimize (disk) I/O opera ons. This metric is called
I/O complexity.
Because merge sort relies on sequen al data access,
it is rela vely easy to transform into an I/O-efficient
external-memory algorithm
Rough idea of external merge sort: Sort pieces that
fit in RAM and then merge them
Two-Way External Merge Sort
Pass 1: Read a page, sort it, write it.
only one buffer page is used
three buffer pages are used to merge two files into one
INPUT 1
OUTPUT
INPUT 2
Main memory buffers Disk

Disk
Two-Way External Merge Sort
3,4 6,2 9,4 8,7 5,6 3,1 2 Input file
Each pass we read + write each PASS 0
page in file. 3,4 2,6 4,9 7,8 5,6 1,3 2 1-page runs
N pages in the file => the PASS 1
4,7 1,3
number of passes 2,3
8,9 5,6 2
2-page runs
4,6
PASS 2
log2 N 1 2,3
4,4 1,2 4-page runs
So I/O complexity is: 6,7 3,5
8,9 6
2 N log 2 N 1 PASS 3
1,2
2,3
Idea: Divide and conquer: sort 3,4
subfiles and merge 4,5
8-page runs
6,6
7,8
9
-
More than 3 buffer pages. How can we utilize them?
To sort a file with N pages using B buffer pages:
Pass 0: use B buffer pages. Produce N/B sorted runs
of B pages each.
B-1 runs.
INPUT 1
... INPUT 2
... OUTPUT ...
INPUT B-1
Disk Disk
B Main memory buffers
Analysis of Mul -Way External Merge Sort
Number of passes: 1 log B 1 N / B

I/O Complexity = 2N * (# of passes)
A mul -way merge that uses all available
buffers requires fewer passes

Advanced Algorithm Analysis: Muhammad Nadeem July 15, 2017

Uploaded by

Copyright:

Available Formats

Advanced Algorithm Analysis: Muhammad Nadeem July 15, 2017

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Advanced Algorithm Analysis: Muhammad Nadeem July 15, 2017

Uploaded by

Copyright:

Available Formats

Advanced Algorithm Analysis

July 15, 2017

cn/ 4 cn/ 4 cn/ 4 cn/ 4 cn

The master method cannot be used to solve

Main memory buffers Disk

Number of passes: 1 log B 1 N / B

You might also like