Recurrence RelationsAlgorithm AnalysisTime ComplexityExamplesSlide 5Recurrence RelationUsesFibonacci SequenceMandlebrot SetExampleExample 2Example 2 Cont.Main Recurrence TheoremUsing the MRTSlide 15Putting it all TogetherQuestionsWorks CitedRecurrence RelationsBy: Sean LynMarch 25, 2008Algorithm Analysis•“The process of deriving the estimates for the time and space required to execute an algorithm.”•Direct Proof•Proof by Contradiction•Proof by InductionTime Complexity•Θ(g(n)) = is g(n)•O(g(n)) = is at most g(n)•Ω(g(n)) = is at least g(n)Examples•for (x=0; x<n; x++) a+=1;•for (x=0; x<n; x++){ for (y=0; y<n; y++) a+=1; }log n n n2n32nn!1 1 1 1 1 2 110 ≈3 10 100 1,000 1,024 3,628,800100 ≈7 100 10,000 1,000,000 1.3*10309.3*101571,000 ≈10 1,000 1,000,000 1*1091.1*103014.0*10256710,000 ≈13 10,000 1*1081*10122.0*103010---100,000 ≈17 100,000 1*10101*1015--- ---1,000,000 ≈20 1,000,000 1*10121*1018--- ---Algorithm EfficiencyRecurrence Relation•“A recurrence relation relates the nth element of a sequence to [a] certain of its predecessors”•In other words, how do you define An in terms of A1,A2,A3,… An-1 ?Uses•Used for describing the time required by an algorithm•It can be used in defining a sequenceFibonacci Sequence•Fn = Fn-1 + Fn-2 where n > 2, F1 = 1, and F2 = 1Mandlebrot Set•Zn+1 = (Zn)² + C, Z0 = CExample•Cn is the number of times the statement x=x+1 executes example(n) { if (n==1) return; for (i=1; x<n; x++) x = x+1; example(n/2); } C1 = 0We get the recurrence relation Cn = n + C[n/2]Example 2•Solving a recurrence relation, or producing a solution without using Ci for any i.•Given: Cn = Cn-1 + n, n>=1 and C0 = 0•Cn-1 = Cn-2 + n-1 -> Cn = (Cn-2+n-1)+n•Repeat…Example 2 Cont.•Cn = Cn-1 + n•Cn = Cn-2 + (n-1) + n•Cn = Cn-3 + (n-2) + (n-1) + n•Which gives us…•Cn = C1 + 2 + 3 + … (n-2) + (n-1) + n•Cn = C0 + 1 + 2 + … (n-2) + (n-1) + n•Cn = 0 + 1 + 2 +…. n•Cn = n(n+1)/2Main Recurrence Theorem•Let a, b and k be integers satisfying a>=1, b >= 2, and k >= 0.•The recurrence relation must have the form: T(n) = aT(n/b) + f(n), where f(n) = O(nk) / O(nk) if a < bk•T(n) = | O(nklogn) if a = bk \ O(nlogba) if a > bkThis also applies to Θ and ΩUsing the MRT•Find O() for the relation•T(n) = 2T(n/2) + n•a = 2, b = 2, k = 1•We can see that 2 = 2¹•Therefore a = bk so we get O(nlogn)Example 2•Find O() for the relation•T(n) = 3T(n/2) + n²•a = 3, b = 2, k = 2•We can see that 3 < 2²•Therefore a < bk so we get O(n²)Putting it all Together•Recurrence relations can be used to define the time complexity of an algorithm•Recurrence relations can be used to define sequences•Time complexities are important because computers have limited memory.•The main recurrence theorem can be used to solve the time complexities of recurrence relationsQuestions•What is one example of a sequence generated by a recurrence relation?•Using the MRT, what is the time complexity of the function: T(n) = T(n)+n ?Works Cited•Johnsonbaugh, Richard and Marcus Schaefer. Algorithms. New Jersey: Pearson Education, Inc, 2004.•“Recurrence Equation.” http://mathworld.wolfram.com. 2008. 25 March 2008.
View Full Document
Unlocking...