Bounding Facts : Bounding Facts Prof. Dan Barrish-Flood
Algorithms (su04)
More Bounding Facts : More Bounding Facts If f(n) = o(g(n)), then f(n) ¹ Q(g(n))
Proof:
Assume
More Bounding Facts (continued) : More Bounding Facts (continued)
So eventually ( for n large enough)
Summations : Summations
Common Summations : Common Summations
Slide6 : In general: divide by (r – 1)
Running Times for Some Simple Iterative Algorithms : Running Times for Some Simple Iterative Algorithms CLEAR-MATRIX(A[1 ¼ n,1¼n])
1 for i ¬ 1 to n
2 do for j ¬ 1 to n
3 do A[i,j]=0
Slide8 : Running Times for Some Simple Iterative Algorithms (continued) IDENTITY-MATRIX(A[1 ¼ n,1¼n])
1 CLEAR-MATRIX(A)
2 for i ¬ 1 to n do
3 do A[i,i]=1
same asymptotic running time as CLEAR-MATRIX
Slide9 : CLEAR-LOWER-TRIANGLE(A[1¼n,1¼n])
(including diagonal)
1 for i ¬ 1 to n
2 do for j ¬ 1 to i
3 do A[i,j]=0
Slide10 : CLEAR-UPPER-TRIANGLE(A[1¼n,1¼n])
(including diagonal)
1 for i ¬ 1 to n
2 do for j ¬ i to n
3 do A[i,j]=0
Slide11 : AVERAGE-NEIGHBORS(A[1¼n])
1 for i ¬ 2 to n-1 do
2 sum ¬ 0
3 for j ¬ i-1 to i+1 do
4 sum ¬ sum+A[j]
5 A[i] ¬ sum/3
T(n)=q(n) LINEAR!
{
Mergesort : Mergesort To sort a list of n items:
sort the first half of the list
sort the second half
merge the sorted halves
Sorting 1 or 0 items is trivial.
Merging two sorted lists is easily done in linear (q(n)) time. (Just take the smallest item from each list and put it on the merged list.)
Slide13 : MERGESORT(A[1¼n])
1 if n £ 1 then
2 return A
3 else
4 B ¬MERGESORT(A[1 ¼ ën/2û)
5 C ¬MERGESORT(A[ën/2û+1¼n])
6 return MERGE(B,C)
Mergesort Example : Mergesort Example 1 2 2 3 4 5 6 6 2 4 5 6 1 2 3 6 2 5 5 2 4 6 1 3 2 6 4 6 1 3 2 6 merge merge merge merge merge merge merge sorted sequence The operation of mergesort on the array A= á5,2,4,6,1,3,2,6 ñ. The lengths
of the sorted sequences being merged increases as the algorithm progresses
from bottom to top.
The Call Tree for Mergesort : The Call Tree for Mergesort MS(n/4)
Slide16 : What is the running time of Mergesort?
Let’s call it T(n).
time taken by
recursive calls
T(n) = 2T(n/2) + n
T(1) = 1
This is a recurrence equation, or recurrence for short. T(n) = + time to merge
Solving Recurrences : Solving Recurrences Method 1: Know the answer.
Not recommended as a general technique.
Method 2: Recursion Trees
Good for intuition
Method 3: Telescoping + Transformations
Fairly general
Recursion Trees : Recursion Trees 1. Draw the call tree for the algorithm.
2. Label each node with the work done at that invocation only.
3. Determine the total work done at each level of the tree.
4. Sum the values at each level to get the total running time.
Recursive Factorial : Recursive Factorial T(1) = 1
FACT(n) T(n) = T(n-1) + 1, n ≥ 2
1 if n £ 1 then Call tree:
2 return 1 FACT(n)
3 else |
4 return n*FACT(n-1) FACT(n-1)
|
FACT(n-2)
FACT(1)
Recursion Tree for FACT : Recursion Tree for FACT 1 1
1 1
1 1
1 1
n
Recursion Tree for Mergesort : Recursion Tree for Mergesort n n n/2 n n/4 n
n
n(lgn+1) n/2 n/4 n/4 n/4 total work
at each level lgn + 1
levels n(lgn+1) = nlgn + n = Θ(nlgn)
Telescoping : Telescoping Consider
T(n) = T(n-1) + 1, n≥1
T(0) = 1
(The recurrence for
FACT(n).)
“world’s simplest recurrence” We can solve it like this:
T(n) - T(n-1) = 1
T(n-1) - T(n-2) = 1
T(n-2) - T(n-3) = 1
T(1) - T(0) = 1
T(n) - T(0) = n
T(n) = n+1
Generalizing ... : Generalizing ... The RHS’s can be different from each other - as long as they don’t contain T.
Check
Also... : Also... The LHS doesn’t have to be T(n). All we need is that
expr(n)-expr(n-1) = ...
nT(n) - (n-1)T(n-1) = 1 (n-1)T(n-1) - (n-2)T(n-2) = 1
2T(2) - T(1) = 1
nT(n) - T(1) = n-1
nT(n) = n, T(n) = 1
E.g. nT(n) = (n-1)T(n-1) + 1, T(1) = 1
Finally... : Finally... It doesn’t matter whether the “base case” is T(0), T(1), T(2), etc. - as long as it’s some constant.
Our goal is to get all recurrences into telescoping form.
Domain Transformations : Domain Transformations Consider: T(n) = T(n/2) + 1 , n ³ 2
T(1) = 1 (The recurrence for binary search)
Not in the form we want, which is T(n) = T(n-1) + ...
But let’s do the following:
Slide27 : Our recurrence
T(n) = T(n/2) + 1, n ≥ 2
T(1) = 1
has become
S(k) = S(k-1) + 1, k ≥ 1
S(0) = 1
which telescopes, giving S(k) = k+ 1.
Back-substituting:
T(n) = S(k) = k+1 = lgn+ 1
(since we defined k = lgn.)
Slide28 : Another recurrence:
T(n) = T(n/2) + n, T(1) = 1
Range Transformations : Range Transformations T(n) = 2T(n-1) + 1, T(1) = 1.
The “2” multiplying T(n-1) is the problem.
So let’s multiply through by
(Trust me.) We call this a summing factor. It’s in telescoping form! (recurrence for “Towers of Hanoi “ puzzle.)
Slide32 : Now we are ready to tackle MERGESORT’s recurrence.
T(n) = 2T(n/2) + n, n > 1
T(1) = 1
First, a domain transformation:
world’s simplest recurrence!
Slide33 : We can solve that:
R(k) = k + 1
Back-substituting:
The Telescope/Transformation Method: A Summary : The Telescope/Transformation Method: A Summary 1. Do domain transformations to deal with the argument to T.
E.g. T(n/2) ® S(k-1).
2. Do range transformations to handle multipliers of T.
E.g. 2T(n-1) ®2 T(n-1).
3. Telescope.
4. Check. -(n-1)