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.
Algorithms Appendix II: Solving Recurrences [Fa"?3]Change is certain. Peace is followed by disturbances; departure of evil men by their return.
Such recurrences should not constitute occasions for sadness but realities for awareness, so that one may be happy in the interim. -I Ching [The Book of Changes](c. 1100 BC) Toendurethe idea of the recurrence one needs: freedom from morality; new means against the fact of pain (pain conceived as a tool, as the father of pleasure; there is no cumulative consciousness of displeasure); the enjoyment of all kinds of uncertainty, experimentalism, as a counterweight to this extreme fatalism; abolition of the concept of necessity; abolition of the "will"; abolition of "knowledge-in-itself." - Friedrich NietzscheThe Will to Power(1884) [translated by Walter Kaufmann]Wil Wheaton:Embrace the dark side!
Sheldon:That"s not even from your franchise!
- "The Wheaton Recurrence",Bing Bang Theory, April 12, 2010Solving Recurrences
? Introduction Arecurrenceis a recursive description of a function, or in other words, a description of a function in terms of itself. Like all recursive structures, a recurrence consists of one or morebase casesand one or morerecursive cases. Each of these cases is an equation or inequality, with some function valuef(n)on the left side. The base cases give explicit values for a (typically finite, typically small) subset of the possible values ofn. The recursive cases relate the function valuef(n)to function valuef(k)for one or more integerskIn both presentations, the first line is the only base case, and the second line is the only recursive
case. The same function can satisfymanydifferent recurrences; for example, both of the following recurrences also describe the identity function: f(n) =8 :0ifn=01ifn=1
f(bn=2c)+f(dn=2e)otherwisef(n) =8 :0ifn=02f(n=2)ifnis even andn>0
f(n1)+1ifnis odd We say that a particular functionsatisfiesa recurrence, or is thesolutionto a recurrence, if each of the statements in the recurrence is true. Most recurrences-at least, those that we will encounter in this class-have a solution; moreover, if every case of the recurrence is an equation, that solution is unique. Specifically, if we transform the recursive formula into a recursivealgorithm, the solution to the recurrence is the function computed by that algorithm!©Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License ( Free distribution is strongly encouraged; commercial distribution is expressly forbidden. See for the most recent revision.Algorithms Appendix II: Solving Recurrences [Fa"?3]Recurrences arise naturally in the analysis of algorithms, especially recursive algorithms. In
many cases, we can express the running time of an algorithm as a recurrence, where the recursive cases of the recurrence correspond exactly to the recursive cases of the algorithm. Recurrences are also useful tools for solving counting problems-How many objects of a particular kind exist? By itself, a recurrence is not a satisfying description of the running time of an algorithm or a bound on the number of widgets. Instead, we need aclosed-formsolution to the recurrence; this is anon-recursivedescription of a function that satisfies the recurrence. For recurrenceequations, we sometimes prefer anexactclosed-form solution, but such a solution may not exist, or may be too complex to be useful. Thus, for most recurrences, especially those arising in algorithm analysis, we are satisfied with anasymptoticsolution of the form(g(n)), for some explicit (non-recursive) functiong(n). For recursiveinequalities, we prefer atightsolution; this is a function that would still satisfy the recurrence if all the inequalities were replaced with the corresponding equations. Again, exactly tight solutions may not exist, or may be too complex to be useful, in which case we seek either a looser bound or an asymptotic solution of the formO(g(n))or (g(n)).2 The Ultimate Method: Guess and Confirm
Ultimately, there is only one fail-safe method to solveanyrecurrence: Guess the answer, and then prove it correct by induction. Later sections of these notes describe techniques to generate guesses that are guaranteed to be correct, provided you use them correctly. But if you"re faced with a recurrence that doesn"t seem to fit any of these methods, or if you"ve forgotten how those techniques work, don"t despair! If you guess a closed-form solution and then try to verify your guess inductively, usually either the proof will succeed, in which case you"re done, or the proof will fail, in which caseyour failure will help you refine your guess. Where you get your initial guess is utterly irrelevantⁱ-from a classmate, from a textbook, on the web, from the answer to a different problem, scrawled on a bathroom wall in Siebel, included in a care package from your mom, dictated by the machine elves, whatever. If you can prove that the answer is correct, then it"s correct!2.? Tower of Hanoi
The classical Tower of Hanoi problem gives us the recurrenceT(n) =2T(n1)+1with base caseT(0) =0. Just looking at the recurrence we can guess thatT(n)is something like2n. If we write out the first few values ofT(n), we discover that they are each one less than a power of two. T(0) =0,T(1) =1,T(2) =3,T(3) =7,T(4) =15,T(5) =31,T(6) =63, ..., It looks likeT(n) =2n1might be the right answer. Let"s check.T(0) =0=201Ø
T(n) =2T(n1)+1
=2(2n11)+1[induction hypothesis]=2n1Ø[algebra]ⁱ...except of course during exams, where you aren"t supposed to useanyoutside sources
2 Algorithms Appendix II: Solving Recurrences [Fa"?3]We were right! Hooray, we"re done!Another way we can guess the solution is byunrollingthe recurrence, by substituting it into
itself:T(n) =2T(n1)+1
=2(2T(n2)+1)+1 =4T(n2)+3 =4(2T(n3)+1)+3 =8T(n3)+7 It looks like unrolling the initial Hanoi recurrencektimes, for any non-negative integerk, will give us the new recurrenceT(n) =2kT(nk)+(2k1). Let"s prove this by induction:T(n) =2T(n1)+1Ø[k=0, by definition]
T(n) =2k1T(n(k1))+(2k11)[inductive hypothesis]
=2k12T(nk)+1+(2k11)[initial recurrence forT(n(k1))] =2kT(nk)+(2k1)Ø[algebra] Our guess was correct! In particular, unrolling the recurrencentimes give us the recurrence T(n) =2nT(0)+(2n1). Plugging in the base caseT(0) =0give us the closed-form solutionT(n) =2n1.
2.2 Fibonacci numbers
Let"s try a less trivial example: the Fibonacci numbersFn=Fn1+Fn2with base casesF0=0 andF1=1. There is no obvious pattern in the first several values (aside from the recurrence itself), but we can reasonably guess thatFnis exponential inn. Let"s try to prove inductively that Fncnfor some constantsa>0andc>1and see how far we get. F n=Fn1+Fn2 cn1+cn2["induction hypothesis"] cn??? The last inequality is satisfied ifcncn1+cn2, or more simply, ifc2c10. The smallest value ofcthat works is= (1+p5)=21.618034; the other root of the quadratic equation has smaller absolute value, so we can ignore it. So we havemostof an inductive proof thatFnnforsomeconstant. All that we"re missing are the base cases, which (we can easily guess) must determine the value of the coefficient a. We quickly compute F 0 0=01 =0andF1 1=10.618034>0,
so the base cases of our induction proof are correct as long as1=. It follows thatFnn1 for alln0. What about a matching lower bound? Essentially the same inductive proof implies that Fnnfor some constant, but the only value ofthat works forallnis the trivial=0! 3Algorithms Appendix II: Solving Recurrences [Fa"?3]We could try to find some lower-order term that makes the base case non-trivial, but an easier
approach is to recall that asymptotic ()bounds only have to work forsufficiently largen. So let"s ignore the trivial base caseF0=0and assume thatF2=1is a base case instead. Some more easy calculation gives usF 2 2=120.381966<1
Thus, the new base cases of our induction proof are correct as long as1=2, which implies thatFnn2for alln1. Putting the upper and lower bounds together, we obtain the tight asymptotic boundFn= (n) . Itispossible to get a more exact solution by speculatively refining and conforming our current bounds, but it"s not easy. Fortunately, if we really need it, we can get an exact solution using theannihilatormethod, which we"ll see later in these notes.2.3 Mergesort
Mergesort is a classical recursive divide-and-conquer algorithm for sorting an array. The algorithm splits the array in half, recursively sorts the two halves, and then merges the two sorted subarrays into the final sorted array.MergeSort(A[1..n]):if(n>1) m bn=2cMergeSort(A[1..m])
MergeSort(A[m+1..n])
Merge(A[1..n],m)Merge(A[1..n],m):i 1;j m+1
fork 1ton ifj>nB[k] A[i];i i+1
else ifi>mB[k] A[j];j j+1
else ifA[i]B[k] A[j];j j+1
fork 1tonA[k] B[k]
LetT(n)denote the worst-case running time ofMergeSortwhen the input array has sizen. TheMergesubroutine clearly runs in(n)time, so the functionT(n)satisfies the following recurrence:T(n) =(
(1)ifn=1,Tdn=2e+Tbn=2c+(n)otherwise.
For now, let"s consider the special case wherenis a power of2; this assumption allows us to take the floors and ceilings out of the recurrence. (We"ll see how to deal with the floors and ceilings later; the short version is that they don"t matter.) Because the recurrence itself is given only asymptotically-in terms of()expressions-we can"t hope for anything but an asymptotic solution. So we can safely simplify the recurrence further by removing the"s; any asymptotic solution to the simplified recurrence will also satisfy the original recurrence. (This simplification is actually important for another reason; if we kept the asymptotic expressions, we might be tempted to simplify them inappropriately.)Our simplified recurrence now looks like this:
T(n) =(
1ifn=1,
2T(n=2)+notherwise.
4 Algorithms Appendix II: Solving Recurrences [Fa"?3] To guess at a solution, let"s try unrolling the recurrence.T(n) =2T(n=2)+n
=22T(n=4)+n=2+n =4T(n=4)+2n=8T(n=8)+3n=It looks likeT(n)satisfies the recurrenceT(n) =2kT(n=2k)+knforanypositive integerk. Let"s
verify this by induction. T(n) =2T(n=2)+n=21T(n=21)+1nØ[k=1, given recurrence]T(n) =2k1T(n=2k1)+(k1)n[inductive hypothesis]
=2k12T(n=2k)+n=2k1+(k1)n[substitution] =2kT(n=2k)+knØ[algebra] Our guess was right! The recurrence becomes trivial whenn=2k=1, or equivalently, when k=log2n:T(n) =nT(1)+nlog2n=nlog2n+n.
Finally, we have to put back the"s we stripped off; our final closed-form solution isT(n) = (nlogn).2.4 An uglier divide-and-conquer example
Consider the divide-and-conquer recurrenceT(n) =pnT(pn)+n. This doesn"t fit into the form required by the Master Theorem (which we"ll see below), but it still sort of resembles the Mergesort recurrence-the total size of the subproblems at the first level of recursion isn-so let"sguessthatT(n) =O(nlogn), and then try to prove that our guess is correct. (We could also attack this recurrence by unrolling, but let"s see how far just guessing will take us.) Let"s start by trying to prove an upper boundT(n)anlgnfor all sufficiently largenand some constantato be determined later:T(n) =pnT(pn)+n
pnapnlgpn+n[induction hypothesis] = (a=2)nlgn+n[algebra] anlgnØ[algebra] The last inequality assumes only that1(a=2)logn,or equivalently, thatn22=a. In other words, the induction proof is correct ifnis sufficiently large. So we were right! But before you break out the champagne, what about the multiplicative constanta? The proof worked foranyconstanta, no matter how small. This strongly suggests that our upper bound T(n) =O(nlogn)is not tight. Indeed, if we try to prove a matching lower boundT(n)bnlogn for sufficiently largen, we run into trouble.T(n) =pnT(pn)+n
pnbpnlogpn+n[induction hypothesis] = (b=2)nlogn+n6bnlogn
5Algorithms Appendix II: Solving Recurrences [Fa"?3]The last inequality would be correct only if1>(b=2)logn, but that inequality is false for large
values ofn, no matter which constantbwe choose. Okay, so(nlogn)is too big. How about(n)? The lower bound is easy to prove directly:T(n) =pnT(pn)+nnØ
But an inductive proof of the upper bound fails.
T(n) =pnT(pn)+n
pnapn+n[induction hypothesis] = (a+1)n[algebra] 6an Hmmm. So what"s bigger thannand smaller thannlgn? How aboutnplgn?T(n) =pnT(pn)+npnapn
qlg pn+n[induction hypothesis] = (a=p2)nAElgn+n[algebra] anAElgnfor large enoughnØ Okay, the upper bound checks out; how about the lower bound?quotesdbs_dbs11.pdfusesText_17[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
