2024/10/6FundamentalsoftheAnalysisofAlgorithmEfficiency(III)Example2:ElementuniquenessproblemExample3:MatrixmultiplicationExample4:CountingbinarydigitsPlanforAnalysisofRecursiveAlgorithmsRecurrenceRelationsExample5:Recursiveevaluationofn!SolvingtherecurrenceforT(n)Then,wesubstitutebackintothefirstequation:WestopwhenwegettoT(0):Howmany“+1”termsarethere?Noticeweincreasethemwitheachsubstitution.Wemusthavenofthe“+1”termsbecausewedidnsubstitutions:So,ourclosedformoftheequationis:Example6:TheTowerofHanoiPuzzleSolvingrecurrencefornumberofmovesExample7:Counting#bitsExample8FibonaccinumbersSolvingaX(n)+bX(n-1)+cX(n-2)=0ApplicationtotheFibonaccinumbersComputingFibonaccinumbersComputingFibonaccinumbersTheEndAssignment