程序代写代做代考 algorithm C Recurrences

Recurrences
Recurrences
COMP4500/7500 July 30, 2019
July 30, 2019 1/49

Recurrences
Divide and conquer algorithms
MERGE_SORT(A,p,r) sorts subarray A[p..r]. MERGE(A,p,q,r) takes sorted subarrays A[p,q] and A[q+1,r]
and merges them to produce sorted array A[p, r ]. Assumes MERGE(A,p,q,r) is ⇥(n) where n = r p + 1.
MERGE_SORT(A,p,r)
1 2 3 4 5
ifp1
= 2T (n/2) + ⇥(n) MERGE_SORT(A,p,r)
1 2 3 4 5
ifpc 2 ⇥(1) ifnc
July 30, 2019
15/49

Recurrences
Solving Recurrences
July 30, 2019
16/49
Ther are three general methods for solving a recurrence: [See CLRS Ch4.]
Substitution:
guess an answer and then prove by induction
Iteration:
expand recurrence to formulate a summation, then solve
Master Method:
remember 3 cases for solving recurrences of the form
T(n) = aT(n/b) + f(n)

Recurrences
Substitution
“Guess” a solution, prove by induction.
July 30, 2019 17/49

Recurrences
Substitution: example without asymptotic notation
Given the recurrence:
T(n) = 2 ifn=2
= 2T(n/2)+n ifn=2k fork >1 T(n) = nlgn foralln=2k wherek 1
and then prove it by induction: Base case: T(2) = 2 = 2log2 2
Inductive step: assume T (n/2) = n/2 lg(n/2) for n/2 = 2k 1 and prove for n = 2k:
T(n) = 2T(n/2) + n
= 2(n/2) lg(n/2) + n substitute inductive assumption = n(lgnlg2)+n
= nlgn
we guess that
July 30, 2019 18/49

Recurrences
Substitution: example using asymptotic notation
Given the recurrence (includes floor):
T(n) = 1 ifn=1
= 2T(bn/2c)+n ifn>1
we notice that it is like the previous one, so guess that:
T(n) 2 O(nlgn)
We need to prove by induction that there exist constants
n0,c > 0 such that
8nn0 •0T(n)cnlgn
We have 0  T (n) for n 1, so focus on T (n)  cn lg n part.
July 30, 2019 19/49

Recurrences
Substitution example: boundary conditions
This depends on n0. Which value for n0 should we choose? We can’t choose n0 = 1 since:
T(1)=1 ⇥ c.1.lg1=0
If we choose n0 = 2 then the only values of 2  n directly
dependent on T (1) are T (2) and T (3): T(2)=2T(1)+2=4  c.2.lg2 ifc25
T(3)=2T(1)+3=5  c.3.lg3 ifc3.lg3 So T(n)  cn lg n for base cases n = 2 and n = 3 if c 2.
July 30, 2019
20/49

Recurrences
Substitution example: inductive step
Assume T (n)  cn lg n for bn/2c, i.e.,
T (bn/2c)  cbn/2c lgbn/2c
then prove T(n)  cnlgn, for some suitable c > 0 (find c):
T(n) = 2T (bn/2c) + n
 2(cbn/2c lgbn/2c) + n
 cn lg(n/2) + n
= cnlgncnlg2+n = cnlgncn+n
 cnlgn
substitute inductive assumption
ifc1andn0
Wemustalsohavec2tosatisfythebasecases,son0 =2 and c = 2 will suffice.
July 30, 2019 21/49

Recurrences
Substitution: more on “Guessing”
Consider
T(n) = 2T(bn/2c) + 17 + n
July 30, 2019
22/49
Difference between
T (bn/2c) and T (bn/2c) + 17
is small, so guess same solution.
Guess loose upper and lower bounds, then refine:
T(n) = ⌦(n) T(n) = O(n2)
Try to lower the upper bound and raise the lower bound until convergence.

Recurrences
Substitution: guessing doesn’t always work!
Consider
We guess T (n) = O(n).
T(n) = T(bn/2c) + T(dn/2e) + 1
Inductive step: assume T (bn/2c)  cbn/2c and
T (dn/2e)  cdn/2e and attempt to prove T (n)  cn:
T(n) =  = ⇥
T (bn/2c) + T (dn/2e) + 1
cbn/2c + cdn/2e + 1 substitute inductive assumptions cn+1,
cn !!!!!
Could prove T(n) = O(n2), but that is too weak… Guess was almost right, just an annoying “1” to remove.
July 30, 2019 23/49

Recurrences
Substitution: strengthening the guess
Try strengthening the guess by subtracting a low order term. Guess that:
9c,n0 >0•0T(n)cnb whereb>0 Inductive step: assume for bn/2c and dn/2e and prove for n:
T(n) = T(bn/2c) + T(dn/2e) + 1
 cbn/2c b + cdn/2e b + 1 substitute assumptions = cn2b+1
 cnb ifb1
Boundary conditions: now find c and n0 to also satisfy the boundary conditions…
By making a stronger inductive assumption we can prove a stronger result!
July 30, 2019 24/49

Recurrences
Substitution: guessing incorrectly + bugs in proofs
Consider again: Guess T (n) 2 O(n).
T(n) = 2T(bn/2c) + n Incorrect inductive step:
Assume T (bn/2c)  cbn/2c and prove T (n)  cn:
T(n) = 2T(bn/2c) + n
 2cbn/2c + n substitute inductive assumption  cn+n
= O(n)!!!
But this does not prove that T (n)  cn !!
Each line is “correct”, but it is not a valid inductive proof.
July 30, 2019 25/49

Recurrences
Change of variables
Consider
T (n) = 2T (bpnc) + lg n
Looks hard: try change of variable where m = lg n (ie, n = 2m)
T(2m) = 2T(2m/2) + m Rename: S(m) = T (2m)
S(m) = 2S(m/2) + m so S(m) = ⇥(m lg m).
Change back
T(n) = T(2m) = S(m) = ⇥(mlgm) = ⇥(lgn lglgn)
Magic???
July 30, 2019 26/49

Recurrences
Iteration
Expand (iterate) the recurrence to get a summation. Evaluate the summation.
More maths, but no need to guess!
July 30, 2019 27/49

Recurrences
Iteration example
Consider
T(n) =
T(n) = ⇥(1) ifn1 T(n) = n+3T(bn/4c) ifn>1
n+3T(bn/4c)
ifn>1
if bnc > 1
if b n c > 1 16
= n + 3(bn/4c + 3T(bn/16c))
= n + 3(bn/4c + 3(bn/16c + 3T(bn/64c)))
= n + 3bn/4c + 9bn/16c + 27T (bn/64c)
= n + 3bn/4c + 32bn/42c + 33T (bn/43c)
…
4
= n+3bn/4c+32bn/42c+…+3iT(bn/4ic) ifb n c>1
4i 1 For which value of i do we stop expanding the recurrence?
For the smallest value of i such that bn/4i c  1.
July 30, 2019 28/49

Recurrences
Iteration example continued.
Assuming T (n) = ⇥(1) for n  1, we stop expanding when bn/4ic’1 ⌘ 4i ‘n ⌘ i ‘log4n
We must have i  dlog4 ne since bn/4dlog4 nec  1. It follows that:
T(n) =  
n+3bn/4c+32bn/42c+…+3iT(bn/4ic) ifb n c>1 n + 3bn/4c + 32bn/42c + . . . + 3dlog4 ne⇥(1) 4i1
P3n 32n 33n log n n+ 4 + 42 + 43 +…+⇥(3 4 )
log n log a usinga b =n b
usinglog43<1 n 1(3)i+⇥(3log4n) i=0 4log 3 July 30, 2019 29/49 = 4n+O(n 4 ) = 4n+O(n) = O(n) Recurrences Recursion tree for T (n) = n + 3T (bn/4c) T(n) = n T(⌊n/4⌋) when n>1
July 30, 2019
30/49
T(⌊n/4⌋)
T(⌊n/4⌋)

Recurrences
Recursion tree for T (n) = n + 3T (bn/4c)
T(n) = when ⌊n/ 4⌋>1 n
⌊n/4⌋ ⌊n/4⌋ ⌊n/4⌋
T⌊n/4$⌋ T⌊n/4$⌋T⌊n/4$⌋T⌊n/4$⌋ T⌊n/4$⌋T⌊n/4$⌋T⌊n/4$⌋ T⌊n/4$⌋T⌊n/4$⌋
July 30, 2019
31/49

Recurrences
Recursion tree for T (n) = n + 3T (bn/4c)
T(n) =
n ⌊n/4⌋
⌊n/4$⌋ ⌊n/4$⌋ ⌊n/4$⌋
when ⌊n/ 4$⌋>1
⌊n/4⌋
⌊n/4$⌋ ⌊n/4$⌋ ⌊n/4$⌋
⌊n/4⌋
⌊n/4$⌋ ⌊n/4$⌋ ⌊n/4$⌋
July 30, 2019
32/49

Recurrences
Recursion tree for T (n) = n + 3T (bn/4c)
T(n) =
n ⌊n/4⌋
⌊n/4$⌋ ⌊n/4$⌋ ⌊n/4$⌋
when ⌊n/ 4%⌋=1
⌊n/4⌋
⌊n/4$⌋ ⌊n/4$⌋ ⌊n/4$⌋
⌊n/4⌋
⌊n/4$⌋ ⌊n/4$⌋ ⌊n/4$⌋
July 30, 2019
33/49
T(1) T(1) T(1) T(1) T(1) T(1) • • • T(1) T(1) T(1) T(1) T(1) T(1)

Recurrences
Recursion tree for T (n) = n + 3T (bn/4c)
T(n) =
⌊n/4⌋
()*% + ⌊n/4’⌋ ⌊n/4’⌋ ⌊n/4’⌋
nn
• • •
T(1) T(1) T(1) T(1) T(1) T(1) #()*% +
⌊n/4⌋ ⌊n/4⌋
⌊n/4’⌋ ⌊n/4’⌋ ⌊n/4’⌋ ⌊n/4’⌋ ⌊n/4’⌋ ⌊n/4’⌋ #$⌊n/ %$⌋
3⌊n/4⌋
T(1) T(1) T(1) T(1) T(1) T(1)
• • •
July 30, 2019
34/49

Recurrences
Problems
Lots of maths
You have to work out all the terms, when to stop, and to sum what you get
Sometimes you can start the iteration and guess the answer
If you guess correctly you can abandon the maths and revert to substitution
July 30, 2019 35/49

Recurrences
Some Details
July 30, 2019
36/49
Floors and ceilings can be troublesome.
Work-around: Assume n has correct form to delete them.
(Previous example: n = 4k ).
Technical abuse, but often works well (OK if function “well-behaved”, see problem 4.5, p74 CLR only).
Recursion trees let you see what is going on. See CLRS p89, p91 [3rd] for diagrams.

Recurrences
Master Method: the rough idea
Need to “memorize” 3 cases for solving (some) recurrences of the form
T(n) = aT(n/b) + f(n) where n/b can be bn/bc or dn/be.
In each case we compare nlogb a with f (n):
Case 1 nlogb a “polynomially larger than” f (n)
solution ⇥(nlogb a)
Case 2 nlogb a “same tight asymptotic bound as” f (n)
solution ⇥(nlogb a lg n)
Case 3 f (n) “polynomially larger than” nlogb a and f (n) is “regular”
solution ⇥(f (n))
July 30, 2019 38/49

Recurrences
Master Method: details
Function f(n) is “polynomially larger than” than g(n) when: f(n) 2 ⌦(g(n) ⇥ n✏) for some ✏ > 0
Equivalently:
f(n) 2⌦(n✏) forsome✏>0 g(n)
Is f(n) = n2 polynomially larger than g(n) = n3/2? Yes: n2 2 ⌦(n3/2 ⇥ n1/2)
Is f(n) = log2 n polynomialy larger than g(n) = 1? No: log2 n 2/ ⌦(1 ⇥ n✏) for any ✏ > 0
July 30, 2019
39/49

Recurrences
Master Method: details
Function f (n) is regular when:
af(n/b) < cf(n) for some c < 1 (Most functions satisfy regularity, but still need to check.) July 30, 2019 40/49 Recurrences Master method Recurrence: T (n) = aT ⇣ n ⌘ + f (n) b Case 1 T(n) 2 ⇥(nlogb a) if Case 2 T(n) 2 ⇥(nlogb a lgn) if Case 3 f(n) 2 O(nlogb a✏) f(n) 2 ⇥(nlogb a) f(n) 2 ⌦(nlogb a+✏) for some ✏ > 0
T(n) 2 ⇥(f(n))
if
for some ✏ > 0 forsomec<1 (i.e. regularity) and afncf(n) b July 30, 2019 41/49 Recurrences Master method Recurrence: T (n) = aT ⇣ n ⌘ + f (n) b Case 1 T(n) 2 ⇥(nlogb a) Case 2 T(n) 2 ⇥(nlogb a lgn) Case 3 T(n) 2 ⇥(f(n)) if f(n) nlogb a if f(n) nlogb a 2 O(n✏) 2 ⇥(1) for some ✏ > 0
if f(n) log a
2 ⌦(n✏) n bn
for some ✏ > 0 and af b cf(n) forsomec<1 July 30, 2019 42/49 Recurrences Master method: Merge sort Recurrence:T(n)=2Tn+f(n) wheref(n)2⇥(n) 2 f(n) 2⇥⇣ n ⌘=⇥⇣n⌘=⇥(1) nlogb a nlog2 2 n Hence case 2 and T(n) 2 ⇥(n1 lgn) = ⇥(nlgn) July 30, 2019 43/49 Recurrences Master method: Binary search Recurrence:T(n)=1Tn+f(n) wheref(n)2⇥(1) 2 f(n) =⇥✓ 1 ◆ =⇥✓1◆=⇥(1) nlogb a nlog2 1 1 Hence case 2 and T(n) 2 ⇥(n0 lgn) = ⇥(lgn) July 30, 2019 44/49 Recurrences Master method: Strassen’s matrix multiply Recurrence:T(n)=7Tn+f(n) wheref(n)2⇥(n2) 2 f(n)2⇥✓n2 ◆=⇥✓ 1 ◆ nlogb a nlog2 7 nlog2 72 where log2 7 2 > 0.
Hence case 1 and T(n) 2 ⇥(nlogb a) = ⇥(nlog2 7) ⇡ ⇥(n2.81)
July 30, 2019
45/49

Recurrences
Master method: Example
Recurrence:T(n)=4Tn+f(n) wheref(n)2⇥(n3) 2
f(n) 2⇥✓ n3 ◆=⇥✓n3◆=⇥(n1) nlogb a nlog2 4 n2
Hence case 3 and T (n) 2 ⇥(f (n)) = ⇥(n3) provided af(n/b)  cf(n) for some c < 1 that is ⇣n⌘ ⇣n⌘3 n3 13 3 afb=42 =48=2ncn for c = 1 . 2 July 30, 2019 46/49 Recurrences Master Method leaves gaps July 30, 2019 48/49 Master Method does not apply if functions “larger” but not “polynomially larger”. In case 3 it is not regular See CLRS p99 [3rd] p77 [2nd]; CLR p67 [1st] for a picture of the proof of the master theorem. Recurrences FYI: Extension to Master Theorem Fills a gap in the Master Theorem. If f(n) 2 ⇥(nlogb a lgk n) f (n) is larger, but not polynomially larger Solution: ⇥(nlogb a lgk+1 n) Case 2 (above) is a special case of this when k = 0. See CLRS Ex 4.6-2 p106 [3rd]; Ex 4.4.2, p84 [2nd]; CLR Ex 4.4.4, p72 [1st] July 30, 2019 49/49