[PDF] Recurrences n = 2k for some constant





Previous PDF Next PDF



CS 161 Lecture 3 - 1 Solving recurrences

Last class we introduced recurrence relations such as T(n) = 2T(?n/2?) + n. Typically Here a = 9



Discrete Mathematics II (Spring 2015) - 8.2 Solving Linear

Determine what is the degree of the recurrence relation. • Need to know the general solution equations. • Need to find characteristic equation. • Need to find 



Recurrences

n = 2k for some constant k and leaving out base case and constant in ?). Methods for solving recurrences. 1. Substitution method. 2. Iteration method.



Q1: Exercise 2.3-3 (10 points) Use mathematical induction to show

recurrence. T(n) =2 ifn=2. 2T(n/2) + n if n = 2k for k > 1 is T(n) = n logn. . Base Step: If n = 2



Master Theorem: Practice Problems and Solutions

The Master Theorem applies to recurrences of the following form: 2. T(n)=4T(n/2) + n2. 3. T(n) = T(n/2) + 2n. 4. T(n)=2nT(n/2) + nn.



GENERATING FUNCTIONS AND RECURRENCE RELATIONS

A recurrence recurrence relation is a set of equations Linear Recurrence. Fibonacci Sequence an = an?1 + an?2 n ? 2. ... n=2 n(n ? 1)xn +.



Solving Recurrences

For example the following recurrence (written in two different but standard ways) describes the identity function f (n) = n:.



1.1 Time complexity and Big-Oh notation: exercises

2. A quadratic algorithm with processing time T(n) = cn2 spends T(N) To have the well-defined recurrence assume that n = km with the integer.



Sample Induction Proofs

(?1)nn(n + 1). 2 . Base case: When n = 1 the left side of (1) is (?1)12 = ?1



3. Recurrence 3.1. Recursive Definitions. To construct a recursively

Example 3.2.1. The factorial function f(n) = n! is defined recursively as follows: 1. Initial Condition: f(0) = 1. 2. Recursion: f(n +1)=(n + 1)f(n).



Recurrence Relations - Hong Kong University of Science and

an= 2 n¡1; n ‚1: Given a recurrence relation for a sequence with initial conditions Solving the recurrence relation means to ?nd a formula to express the general termanof the sequence 2 Homogeneous Recurrence Relations Any recurrence relation of the form



Solving Recurrence Relations - Texas A&M University

n 2 and the base cases of the induction proof (which is not the same as the base case of the recurrence!) are n= 2 and n= 3 (We are allowed to do this because asymptotic notation only requires us to prove our statement for n n 0 and we can set n 0 = 2 ) We choose n= 2 and n= 3 for our base cases because when we expand the recurrence



Recurrence Relations - University of Ottawa

Many sequences can be a solution for the same recurrence relation a n = 2a n 1 a n 2; for n 2 The following sequences are solutions of this recurrence relation: I a n = 3n for all n 0 I a n = 5 for all n 0 The initial conditions for a sequence specify the terms before n 0 (before the recurrence relation takes e ect)



Solving Recurrence Relations - Princeton University

n 2 to be C0 and C1 Since the sequences fang and f 1rn 1 + 2r n 2g satisfy the degree 2 recurrence and agree on the rst two values they must be identical Example: Find the solution to the recurrence relation an = an 1 +an 2 with initial condi-tions a0 = 2 and a1 = 7 Solution: The characteristic equation is r2 r 2 = 0 i e (r 2)(r +1) = 0



Recurrence Relations - University of Illinois Urbana-Champaign

2 Recall that 1=nk= nk and we have rn 2(r25r + 6) = 0 Then we can factor the polynomial into rn 2(r 2)(r 3) = 0 We assumed that r is non-zero so we can divide by the rst factor rn 2 which leaves (r 2)(r 3) = 0 Thus the characteristic function (also: polynomial) remains on the left-hand side



Searches related to 2^n n^2 recurrence PDF

n = 2n for every nonnegative integer n is a solution of the recurrence relation a n = 2a n-1 - a n-2 for n = 234 Assume a 0=1 and a 1=2 Solution: Check initial conditions a 0= 20 = 1 a 1= 2 1 = 2 Check if {2n} satisfies a n = 2a n-1 - a n-2 2a n-1 - a n-2 = 2(2n-1) - 2n-2 = 2n-2(4-1) = 3(2n-2) 2n So {2n} is not a solution for a n = 2a

What is the solution of the recurrence relation?

.Thenasequence (a n ) is a solution of the recurrence relation a n= c 1a n?1+ c 2a n?2 if and only if a n= ? 1r n 1+ ? 2r n 2 for n ? 0 for some constants ? 1,? 2 Idea of the Proof The proof proceeds exactly as in the case of the Fibonacci numbers. Try to prove it yourself!

What is the solution of recurrence relation an = 10an-1 - 25an-2?

The solution of the recurrence relation an = 10an-1 - 25an-2, is: (a0 = 1, a1 = 15) Q8. Solution to recurrence relation T (n) = T (n - 1) + 4 is given by, where n > 0 and T (0) = 3.

What is a 2 nd-order linear recurrence?

This is a subset of the type of 2 nd -order recurrence formulas used by MCS . The Fibonacci number s are the best-known example of a 2 nd -order linear recurrence.

What is the initial condition for a recurrence relation?

So (a_n = 3a_ {n-1} + 2) is our recurrence relation and the initial condition is (a_0 = 1 ext {.}) We are going to try to solve these recurrence relations.

Recurrences

(CLRS 4.1-4.2) •Last time we discussed divide-and-conquer algorithms

Divide and Conquer

To Solve P:

1.DivideP into smaller problemsP1,P2,P3.....Pk.

2.Conquerby solving the (smaller) subproblems recursively.

3.Combinesolutions toP1,P2,...Pkinto solution for P.

•Analysis of divide-and-conquer algorithms and in general of recursive algorithms leads to recurrences. •Merge-sort lead to the recurrenceT(n) = 2T(n/2) +n -or rather,T(n) =?Θ(1) Ifn= 1 T(?n

2?) +T(?n2?) + Θ(n) Ifn >1

-but we will often cheat and just solve the simple formula (equivalent to assuming that n= 2kfor some constantk, and leaving out base case and constant in Θ).

Methods for solving recurrences

1. Substitution method

2. Iteration method

•Recursion-tree method •(Master method)

1 Solving Recurrences with the Substitution Method

•Idea: Make a guess for the form of the solution and prove by induction. •Can be used to prove both upper boundsO() and lower bounds Ω(). •Let"s solveT(n) = 2T(n/2) +nusing substitution -Proof: ?Base case: we need to show that our guess holds for some base case (not necessarily n= 1, some smallnis ok). Ok, since function constant for small constantn.

2logn2(Question: Why notn-1?)

T(n) = 2T(n/2) +n

2logn2) +n

=cnlogn 2+n =cnlogn-cnlog2 +n =cnlogn-cn+n

So ok ifc≥1

•Similarly it can be shown thatT(n) = Ω(nlogn)

Exercise!

•Similarly it can be shown thatT(n) =T(?n

2?) +T(?n2?) +nis Θ(nlgn).

Exercise!

•The hard part of the substitution method is often to make a good guess. How do we make a good (i.e. tight) guess??? Unfortunately, there"s no "recipe" for this one. Try iteratively O(n3),Ω(n3),O(n2),Ω(n2) and so on. Try solving by iteration to get a feeling of the growth.

2 Solving Recurrences with the Iteration/Recursion-tree Method

•In the iteration method we iteratively "unfold" the recurrence until we "see the pattern". •The iteration method does not require making a good guess like the substitution method (but it is often more involved than using induction). •Example: SolveT(n) = 8T(n/2) +n2(T(1) = 1)

T(n) =n2+ 8T(n/2)

=n2+ 8(8T(n

22) + (n2)2)

=n2+ 82T(n

22) + 8(n24))

=n2+ 2n2+ 82T(n 22)
=n2+ 2n2+ 82(8T(n

23) + (n22)2)

=n2+ 2n2+ 83T(n

23) + 82(n242))

=n2+ 2n2+ 22n2+ 83T(n 23)
=n2+ 2n2+ 22n2+ 23n2+ 24n2+... -Recursion depth: How long (how many iterations) it takes until the subproblem has constant size?itimes wheren

2i= 1?i= logn

-What is the last term? 8iT(1) = 8logn T(n) =n2+ 2n2+ 22n2+ 23n2+ 24n2+...+ 2logn-1n2+ 8logn logn-1? k=02kn2+ 8logn =n2logn-1? k=02k+ (23)logn •Now?logn-1 k=02kis a geometric sum so we have?logn-1 k=02k= Θ(2logn-1) = Θ(n) •(23)logn= (2logn)3=n3

T(n) =n2·Θ(n) +n3

= Θ(n3)

2.1 Recursion treeA different way to look at the iteration method: is the recursion-tree, discussed in the book (4.2).

•we draw out the recursion tree with cost of single call in eachnode-running time is sum of costs in all nodes •if you are careful drawing the recursion tree and summing up the costs, the recursion tree is a direct proof for the solution of the recurrence, just like iteration and substitution •Example:T(n) = 8T(n/2) +n2(T(1) = 1) (n/2)2(n/2)2 (n/4)

2(n/4)2n

2n2(n/2)

2(n/2)2

T(n/4)n

2

T(n/4)

T(n)1)

T(n/2) T(n/2)n

22)

T(1) T(1)T(1)8(n/2) = 2n

8 (n/4) = 2 n2 2

2 2 22 log n

8 T(1)+

+3) log n) T(n) =n2+ 2n2+ 22n2+ 23n2+ 24n2+...+ 2logn-1n2+ 8logn

3 Matrix Multiplication

•LetXandYben×nmatrices

11x12···x1n

x

21x22···x1n

x

31x32···x1n

x •We want to computeZ=X·Y -zij=?nk=1Xik·Ykj •Naive method uses?n2·n= Θ(n3) operations •Divide-and-conquer solution:Z=?A B C D?

·?E F

G H? =?(A·E+B·G) (A·F+B·H) (C·E+D·G) (C·F+D·H)? -The above naturally leads to divide-and-conquer solution: ?DivideXandYinto 8 sub-matricesA,B,C, andD. ?Do 8 matrix multiplications recursively. ?ComputeZby combining results (doing 4 matrix additions). -Lets assumen= 2cfor some constantcand letA,B,CandDben/2×n/2 matrices ?Running time of algorithm isT(n) = 8T(n/2) + Θ(n2)?T(n) = Θ(n3) -But we already discussed a (simpler/naive)O(n3) algorithm! Can we do better?

3.1 Strassen"s Algorithm

•Strassen observed the following:Z=?A B C D?

·?E F

G H? =?(S1+S2-S4+S6) (S4+S5) (S6+S7) (S2+S3+S5-S7)? where S

1= (B-D)·(G+H)

S

2= (A+D)·(E+H)

S

3= (A-C)·(E+F)

S

4= (A+B)·H

S

5=A·(F-H)

S

6=D·(G-E)

S

7= (C+D)·E

-Lets test thatS6+S7is reallyC·E+D·G S

6+S7=D·(G-E) + (C+D)·E

=DG-DE+CE+DE =DG+CE •This leads to a divide-and-conquer algorithm with running timeT(n) = 7T(n/2) + Θ(n2) -We only need to perform 7 multiplications recursively. -Division/Combination can still be performed in Θ(n2) time. •Lets solve the recurrence using the iteration method

T(n) = 7T(n/2) +n2

=n2+ 7(7T(n

22) + (n2)2)

=n2+ (7

22)n2+ 72T(n22)

=n2+ (7

22)n2+ 72(7T(n23) + (n22)2)

=n2+ (7

22)n2+ (722)2·n2+ 73T(n23)

=n2+ (7

22)n2+ (722)2n2+ (722)3n2....+ (722)logn-1n2+ 7logn

logn-1? i=0(7

22)in2+ 7logn

=n2·Θ((7

22)logn-1) + 7logn

=n2·Θ(7logn (22)logn) + 7logn =n2·Θ(7logn n2) + 7logn = Θ(7 logn) -Now we have the following: 7 logn= 7log 7n log72 = (7 log7n)(1/log72) =n(1/log72) =nlog 27
log22 =nlog7 -Or in general:alogkn=nlogka So the solution isT(n) = Θ(nlog7) = Θ(n2.81...) •Note: -We are "hiding" a much bigger constant in Θ() than before. -Currently best known bound isO(n2.376..) (another method). -Lower bound is (trivially) Ω(n2).

4 Master Method

•We have solved several recurrences usingsubstitutionanditeration. •we solved several recurrences of the formT(n) =aT(n/b) +nc(T(1) = 1). -Strassen"s algorithm?T(n) = 7T(n/2) +n2(a= 7,b= 2, andc= 2) -Merge-sort?T(n) = 2T(n/2) +n(a= 2,b= 2, andc= 1). •It would be nice to have a general solution to the recurrenceT(n) =aT(n/b) +nc. •We do!

T(n) =aT?nb?+nca≥1,b≥1,c >0

T(n) =?????Θ(nlogba)a > bc

Θ(nclogbn)a=bc

Θ(nc)a < bc

Proof (Iteration method)

T(n) =aT?n

b?+nc =nc+a??n b? c+aT?nb2?? =nc+?a bc?nc+a2T?nb2? =nc+?a bc?nc+a2??nb2? c+aT?nb3?? =nc+?a bc?nc+?abc?2nc+a3T?nb3? =nc+?a =nc?logbn-1 k=0?a bc?k+alogbn =nc?logbn-1 k=0?a bc?k+nlogba

Recall geometric sum

?nk=0xk=xn+1-1 x-1= Θ(xn) •a < bc a < bc?abc<1??logbn-1 a < b c?logba T(n) =nc?logbn-1 k=0?a bc?k+nlogba =nc·Θ(1) +nlogba = Θ(nc) a=bc a=bc?abc= 1??logbn-1 k=0?abc?k=?logbn-1 k=01 = Θ(logbn) a=bc?logba= logbbc=c

T(n) =?logbn-1

k=0?a bc?k+nlogba =ncΘ(logbn) +nlogba = Θ(nclogbn) a > bc a > bc?abc>1??logbn-1 k=0?abc?k= Θ??abc?logbn? = Θ?alogbn(bc)logbn? = Θ?alogbnnc?

T(n) =nc·Θ?alogbn

nc? +nlogba = Θ(nlogba) +nlogba = Θ(nlogba) •Note: Book states and proves the result slightly differently(don"t read it).

5 Changing variables

Sometimes reucurrences can be reduced to simpler ones bychanging variables •Example: SolveT(n) = 2T(⎷ n) + logn

Letm= logn?2m=n?⎷

n= 2m/2

T(n) = 2T(⎷

n) + logn?T(2m) = 2T(2m/2) +m

LetS(m) =T(2m)

T(2m) = 2T(2m/2) +m?S(m) = 2S(m/2) +m

?S(m) =O(mlogm) ?T(n) =T(2m) =S(m) =O(mlogm) =O(lognloglogn)

6 Other recurrencesSome important/typical bounds on recurrences not covered by master method:

•Logarithmic: Θ(logn) -Recurrence:T(n) = 1 +T(n/2) -Typical example: Recurse on half the input (and throw half away) -Variations:T(n) = 1 +T(99n/100) •Linear: Θ(N) -Recurrence:T(n) = 1 +T(n-1) -Typical example: Single loop -Variations:T(n) = 1+2T(n/2),T(n) =n+T(n/2),T(n) =T(n/5)+T(7n/10+6)+n •Quadratic: Θ(n2) -Recurrence:T(n) =n+T(n-1) -Typical example: Nested loops •Exponential: Θ(2n) -Recurrence:T(n) = 2T(n-1)quotesdbs_dbs11.pdfusesText_17
[PDF] la composante vivante dun milieu naturel

[PDF] les composantes de lenvironnement 6ème

[PDF] quelles sont les composantes de lenvironnement

[PDF] les composantes de l'environnement svt 6ème

[PDF] les composantes dun milieu naturel

[PDF] quelles sont les composantes dun milieu naturel

[PDF] les elements qui composent l'environnement

[PDF] les composantes de lenvironnement pdf

[PDF] 1.1.1 tenue des dossiers fournisseurs et sous-traitants

[PDF] 1.1.4 evaluation et suivi des stocks

[PDF] 1.2.3 traitement des devis des commandes

[PDF] 1.2.4 traitement des livraisons et de la facturation

[PDF] 1.3.1 suivi de la trésorerie et des relations avec les banques

[PDF] tenue des dossiers clients donneurs d ordre et usagers

[PDF] 2.2.3 suivi administratif des carrières