Analysis Framework for Analysis of Algorithms.pdf

This presentation contains Algorithm Analysis Framework, Asymptotic Notations, Analysis of Non-Recursive and Analysis of Recursive Algorithms.;
Empirical Analysis of Algorithms; and Algorithm Visualization.

1. Fundamentals of
Analysis of Algorithm Efficiency
Dr.Kiran K
Associate Professor
Department of CSE
UVCE
Bengaluru, India.

2. The Analysis Framework
Measuring an Input’s Size
•AnAlgorithm’sEfficiencyisinvestigatedasafunctionofsomeparameternindicatingthe
Algorithm’sInputSizebecausealmostallalgorithmsrunlongeronlargerinputs.
Eg.:1)Sorting,Searching - Sizeofthelist.
2) Evaluating a Polynomialof degree n - Polynomial’s Degree
Numberof its Coefficients.
3) Product of Two n* nMatrices - Matrix Order, n
TotalNumber of Elements, N.
4)PrimalityofaPositiveIntegerN - Number’sMagnitude(Numberof
bitsinthebinaryrepresentationofn,
b=log
2n+1)
5)ThechoiceofanappropriateSizemetriccanbeinfluencedbyOperationsofthe
algorithminquestion.
Eg.:Spell-CheckingAlgorithm-NumberofCharacters(IfCharactersareexamined)
NumberofWords(IfWordsareexamined)

3. The Analysis Framework…
Units for Measuring Running Time
1.StandardUnitofTimeMeasurement:
•Second,Millisecond,etc.
•Drawbacks:
Dependenton:
SpeedofComputer.
QualityoftheProgram.
Compiler
DifficultyinClockingtheactual
RunningTime.
2.StepCount:
•CounttheNumberofTimesEachoftheAlgorithm’sOperationisExecuted.
•Drawbacks:
ExcessivelyDifficult.
UsuallyUnnecessary.
3.OperationCount,C(n):
•IdentifytheBasicOperation–Most
ImportantOperationcontributingthe
mosttotheTotalRunningTime.
Eg.:Sorting-KeyComparison
MathematicalProblems-/,*,-,+
•ComputeC(n),theNumberof
TimesBasicOperationisexecuted
oninputsofsizen.

4. The Analysis Framework…
Estimating Running Time, T (n) of a Program, given C (n):
T(n) = C
op * C (n).
where, C
op–Execution Time of Basic Operation on a particular Computer.
1. How much faster would an algorithm run
on a machine that is 10 times faster ?
Let, T
1(n) = C
op * C (n)⸫T
2(n) =
1
10
C
op * C (n)
??????2(�)
??????1(�)
≈
1
10
Cop∗C(n)
C
op∗C(n)
= 10
2. How much longer will the algorithm run if the
input is doubled ?
Let,C(n)=
1
2
n(n–1)=
1
2
n
2
–
1
2
n≈
1
2
n
2
??????(2�)
??????(�)
≈
??????
��
??????(2�)
??????
��
??????(�)
≈
1
2
2�
2
1
2
�
2
=4
Note:
1.Thequestionisansweredwithoutactually
knowingthevalueofC
op.
Itgotcancelled.
2.MultiplicativeConstantintheformulafor
thecountC(n),wasalsocancelledout.
1and2→Efficiencyanalysisframework
ignoresMultiplicativeConstantsand
concentratesonthecount’sorderofgrowth.

5. The Analysis Framework…
Orders of Growth
•Measure of an Algorithms’ Efficiency with Variationin Input Size.

6. The Analysis Framework…
Worst Case, Best Case and Average Case Efficiencies
Algorithm’s Efficiencydepends on –Input Size +Specificsof a particular Input.
→Algorithm has Worst, Bestand Average Case Efficiencies
WorstCaseEfficiency:
Efficiencyforinputsofsizenfor
whichthealgorithmrunstheLongest
amongallpossibleinputsofthatsize.
HowtoDetermine?
FindinputsthatyieldtheLargest
valueofC(n)amongallpossible
inputsofsizen.
BestCaseEfficiency:
Efficiencyforinputsofsizenfor
whichthealgorithmrunstheFastest
amongallpossibleinputsofthatsize.
HowtoDetermine?
FindinputsthatyieldtheSmallest
valueofC(n)amongallpossible
inputsofsizen.

7. The Analysis Framework…
AverageCaseEfficiency
EfficiencyforaRandomInputofsizen.
SomeAssumptionsaboutpossibleinputsofsizenneedstobemadewhileanalyzing.
ConsiderablyMoreDifficultthattheothertwo.
HowtoDetermine?
DivideAllInstancesofsizenintoSeveralClassessothatforeachinstanceofthe
classtheNumberofTimesthealgorithm’sBasicOperationisexecutedistheSame.
ObtainorAssumeaProbabilityDistributionofinputsandfindtheexpectedvalue
ofthebasicoperation’scount.
AmortizedEfficiency
ItappliesnottoasinglerunofanalgorithmbutrathertoaSequenceofOperations.

8. The Analysis Framework…
BestCase:
NotnearlyImportant.
Forsomealgorithmsagoodbest-case
performanceextendstosomeusefultypesof
InputsclosetobeingtheBest-Caseones.
IfUnsatisfactory,thealgorithmcanbe
Discardedimmediatelywithoutfurtheranalysis.
WorstCase:
ProvidesveryImportant
informationaboutanalgorithm’s
efficiency-Boundsrunning
timefromAbove.
AverageCase:
NeededbecausetheAverage-Case
efficiencyofmanyimportant
algorithmsisBetterThanthe
Worst-Caseefficiency.
Cannotbeobtainedbytakingthe
averageoftheWorst-Caseandthe
Best-Caseefficiencies.
DiscussiononEfficiencies:
AmortizedEfficiency:
InsomesituationsaSingleOperationcanbe
Expensive,butthetotaltimeforanentiresequence
ofnsuchOperationsisalwayssignificantlybetter
thantheworst-caseefficiencyofthatsingle
operationmultipliedbyn.

9. The Analysis Framework…
SequentialSearch:
Searchforagivenitem,KeyK,inalistofnelements.
CheckSuccessiveElementsofthelistUntileitheraMatchisfoundorthelistis
Exhausted.
AlgorithmSequentialSearch(A[0..n−1],K)
i← 0
while(i<nandA[i] ≠K) do
i← i+ 1
if(i<n)
returni
else
return−1

10. WorstCase:
•ItoccurswhenthereareNoMatching
Elementsorthefirstmatchingelement
happenstobetheLastOneonthelist.
•NumberofkeyComparisonswillbe
equaltotheNumberofElementsinlist.
i.e. C
worst(n) = n
BestCase:
•ItoccurswhentheFirstElementinthe
listequalstotheSearchKey.
•NumberofkeyComparisonswillbe
equalto1.
i.e. C
best(n) = 1
AverageCase:
Assumptions:
•ProbabilityofSuccessfulSearch=p(0≤p≤1).
•ProbabilityofthefirstMatchoccurringinthe
i
th
PositionofthelististheSameforeveryi.
SuccessfulSearch:
•ProbabilityofthefirstMatchoccurringinthe
i
th
Positionisp/nforeveryi.
•NumberofComparisonsmadeisequaltoi.
UnsuccessfulSearch:
•Probability=(1–p).
•NumberofComparisonsmadeisequalton.
C
avg(n)=1.
&#3627408477;
&#3627408475;
+2.
&#3627408477;
&#3627408475;
+...+??????.
&#3627408477;
&#3627408475;
+...+??????.
&#3627408477;
&#3627408475;
+n.(1–p)
=
&#3627408477;
&#3627408475;
1+2+...+??????+...+??????+n.(1–p)
=
&#3627408477;
&#3627408475;
&#3627408475;(&#3627408475;+1)
2
+n.(1–p)=
&#3627408477;(&#3627408475;+1)
2
+n.(1–p)
Successful Search:
p= 1
⸫C
avg(n) =
&#3627408475;+1
2
Unsuccessful Search:
p= 0
⸫C
avg(n) = n

11. Asymptotic Notations
•t(n)andg(n)-NonnegativeFunctionsdefinedonthesetofnaturalnumbers.
•t(n)-Algorithm’sRunningTimeindicatedbyitsbasicoperationcountC(n).
•g(n)-SomeSimpleFunctiontoComparethecountwith.
Afunctiont(n)issaidtobeinO(g(n)),
denotedt(n)∈O(g(n)),ift(n)is
boundedAbovebysomeconstant
multipleofg(n)foralllargen,
i.e.,
Ifthereexistsomepositiveconstantcand
somenonnegativeintegern
0suchthat
t (n) ≤ c * g (n) for all n ≥ n
0
Ο(Big Oh) Notation:

12. Asymptotic Notations…
Afunctiont(n)issaidtobeinΩ(g(n)),
denotedt(n)∈Ω(g(n)),ift(n)is
BoundedBelowbysomeconstant
multipleofg(n)foralllargen,
i.e.,
Ifthereexistsomepositiveconstantcand
somenonnegativeintegern
0suchthat
t (n) ≥c * g (n) for all n ≥ n
0
Ω(Big Omega) Notation:

13. Asymptotic Notations…
Afunctiont(n)issaidtobeinΘ(g(n)),
denotedt(n)∈Θ(g(n)),ift(n)is
BoundedbothAboveandBelowbysome
constantmultiplesofg(n)foralllargen,
i.e.,
Ifthereexistsomepositiveconstantsc
1
andc
2andsomenonnegativeintegern
0
suchthat
c
2g (n) ≤ t (n) ≤ c
1g (n)for all n ≥ n
0
Θ(Big Theta) Notation:

14. Asymptotic Notations…
Theorem:
If t
1(n)∈O (g
1(n)) and t
2(n)∈O (g
2(n)), then
t
1(n)+t
2(n)∈O (max {g1 (n), g2 (n)})
Proof:
t
1(n)Є O (g
1(n))→ t
1(n) ≤ c
1g
1(n) for all n ≥ n
1 (1)
t
2(n) Є O (g
2(n)) → t
2(n) ≤ c
2g
2(n) for all n ≥ n
2 (2)
(1) + (2) gives
t
1(n)+ t
2(n) ≤ c
1 g
1(n)+ c
2 g
2(n)
≤ c
3 g
1(n)+ c
3 g
2(n)[⸪c
3 = max{ c
1 , c
2 }]
≤ c
3 [ g
1(n) +g
2(n) ]
≤ 2 c
3 max { g
1(n) , g
2(n) }
t
1(n) + t
2(n) ≤ O (max { g
1(n) , g
2(n) })

15. Basic Efficiency Classes
Class Name
1 Constant
log n Logarithmic
n Linear
n log n Linearithmic
n
2
Quadratic
n
3
Cubic
2
n
Exponential
n! Factorial

16. Mathematical Analysis of NonrecursiveAlgorithms
General Plan for Analyzing the Time Efficiency of NonrecursiveAlgorithms
1.Decideonaparameter(orparameters)indicatinganInput’sSize.
2.Identifythealgorithm’sBasicOperation.
3.CheckwhethertheNumberofTimestheBasicOperationisexecuteddepends
onlyontheSizeofanInput.IfitalsodependsonsomeAdditionalProperty,the
Worst-case,Average-case,and,ifnecessary,Best-caseefficiencieshavetobe
investigatedseparately.
4.SetupaSumexpressingtheNumberofTimestheBasicOperationisexecuted.
5.Usingstandardformulasandrulesofsummanipulation,eitherfindaClosedForm
Formulaforthecountor,attheveryleast,establishitsOrderofGrowth.

17. Mathematical Analysis of NonrecursiveAlgorithms…
Example 1:Find the Value of the Largest Element in a List.
•InputSize
•BasicOperation
:NumberofElementsintheList,n
:ComparisonOperation,A[i]>maxval
•Numberoftimesthecomparisonoperationisexecuteddependsonlyonthesizeofthelist.
→NoBest,Worst,AverageCases.
•LetC(n)denotethenumberofTimesthecomparisonoperation,A[i]>maxval,isexecuted.
AlgorithmMaxElement(A[0..n−1])
maxval← A[0]
for(i=1 to n –1) do
if(A[i] >maxval)
maxval← A[i]
returnmaxval
Thecomparisonoperationisexecutedoncefor
eachvalueoftheloopvariableifrom1ton–1.
=
&#3627408470;=1
&#3627408475;−1
1⸫C(n) =(n –1) –1 + 1
=n –1 –1 + 1=n –1
ЄΘ(n)

18. Mathematical Analysis of NonrecursiveAlgorithms…
Example 2:Check whether all elements in a given List are distinct.
AlgorithmUniqueElements(A[0..n−1])
for(i=0 to n -2) do
for(j=i+ 1 to n -1) do
if(A[i] = A [j])
returnfalse
returntrue
•InputSize
•BasicOperation
:NumberofElementsintheList,n
:ComparisonOperation,A[i]=A[j]
•Numberoftimesthecomparisonoperationisexecuteddependsnotonlyonthesizeofthelist.
But,alsoonthePositionsoftheequalelements,ifpresent.→Best,WorstAverageCases.
•LetC(n)denotethenumberofTimesthecomparisonoperation,A[i]=A[j],isexecuted.

19. Mathematical Analysis of NonrecursiveAlgorithms…
BestCase:
Itoccurswhen
FirstTwoElementsinthe
listareEqual.
= 0 –0 + 1
= 1
ЄΘ(1)
WorstCase:
Itoccurswheneither
NoElementsareEqual.
LastTwoElementsareEqual.
=
(??????
2
−??????)
2
=
(??????−1)(??????−1+1)
2
=
(??????−1)(??????)
2
ЄΘ(n
2
)≈n
2
=
&#3627408470;=0
0

&#3627408471;=&#3627408470;+1
&#3627408470;+1
1⸫C(n)
=
&#3627408470;=0
0
??????+1−??????+1+1
=
&#3627408470;=0
0
??????+1−??????−1+1=
&#3627408470;=0
0
1
=
&#3627408470;=0
&#3627408475;−2

&#3627408471;=&#3627408470;+1
&#3627408475;−1
1⸫C(n) =
&#3627408470;=0
&#3627408475;−2
??????−1−??????+1+1
=
&#3627408470;=0
&#3627408475;−2
??????−1−??????−1+1=
&#3627408470;=0
&#3627408475;−2
??????−??????−1
= (n–1–0)+(n–1–1)+...+(n–1–(n–2))
= (n–1–0)+(n–1–1)+...+(n–1–n+2))
= (n–1)+(n–2)+...+1
=
??????−1((??????−1)+1)
2
for(i=0 to n -2) do
for(j=i+ 1 to n -1) do
if(A[i] = A [j])

20. Mathematical Analysis of NonrecursiveAlgorithms…
Example 3:Matrix Multiplication.
AlgorithmMatrixMultiplication(A[0..n−1,0..n–1],B[0..n−1,0..n–1])
for(i=0 to n –1) do
for(j=0to n –1) do
C [i, j] ← 0
for(k=0 to n –1) do
C [i, j] =C [i, j] +A [i, k]*B [k, j]
returnC
•InputSize
•BasicOperation
:OrderoftheMatrix,n
:MultiplicationOperation,A[i,k]*B[k,j]
•NumberoftimesthemultiplicationoperationexecuteddependsonlyonthesizeoftheMatrix.
→NoBest,Worst,AverageCases.

21. Mathematical Analysis of NonrecursiveAlgorithms…
•LetC(n)denotethenumberoftimesthemultiplicationoperation,A[i,k]*B[k,j],is
executed.
=
&#3627408470;=0
&#3627408475;−1

&#3627408471;=0
&#3627408475;−1

&#3627408472;=0
&#3627408475;−1
1=
&#3627408470;=0
&#3627408475;−1

&#3627408471;=0
&#3627408475;−1
??????−1−0+1=
&#3627408470;=0
&#3627408475;−1

&#3627408471;=0
&#3627408475;−1
??????−1−0+1
=
&#3627408470;=0
&#3627408475;−1

&#3627408471;=0
&#3627408475;−1
??????=??????
&#3627408470;=0
&#3627408475;−1

&#3627408471;=0
&#3627408475;−1
1=??????
&#3627408470;=0
&#3627408475;−1
??????−1−0+1=??????
&#3627408470;=0
&#3627408475;−1
??????−1−0+1
=??????
&#3627408470;=0
&#3627408475;−1
??????=??????
2

&#3627408470;=0
&#3627408475;−1
1=??????
2
((n–1) –0 + 1)=??????
2
(n–1 –0 + 1)
=??????
3
=??????
2
(n)
ЄΘ(n
3
)
⸫C(n)

22. Mathematical Analysis of NonrecursiveAlgorithms…
Example 4:Number of binary digits in the binary representation of a positive decimal integer.
AlgorithmBinary(n)
Count←1
while (n >1) do
Count ← Count + 1
n← n/2
returnC
•InputSize
•BasicOperation
:Number,n
:DivisionOperation,n/2
•NumberoftimesthedivisionoperationisexecuteddependsonlyontheNumber→NoBest,
Worst,AverageCases.
•LetC(n)denotethenumberoftimesthedivisionoperation,n/2,isexecuted
⸫C(n)
=
&#3627408470;=1
log&#3627408475;
1
=(logn–1) + 1)
=logn–1+ 1)
≈lognЄΘ(logn)

23. Mathematical Analysis of Recursive Algorithms
General Plan for Analyzing the Time Efficiency of NonrecursiveAlgorithms
1.Decideonaparameter(orparameters)indicatinganInput’sSize.
2.Identifythealgorithm’sBasicOperation.
3.Checkwhetherthenumberoftimesthebasicoperationisexecutedcanvaryon
differentinputsofthesamesize;ifitcan,theWorst-case,Average-case,andBest-
caseefficienciesmustbeinvestigatedseparately.
4.SetupaRecurrenceRelation,withanappropriateinitialcondition,forthenumber
oftimestheBasicOperationisexecuted.
5.Solvetherecurrenceor,atleast,ascertaintheOrderofGrowthofitssolution.

24. Mathematical Analysis of Recursive Algorithms…
Example 1:Computing Factorial, Fact (n) = n!
AlgorithmFact(n)
if (n =0)
return1
else
return(Fact (n –1) *n)
•InputSize
•BasicOperation
:Number,n
:MultiplicationOperation,Fact(n–1)*n
•NumberoftimestheMultiplicationoperationisexecuteddependsonlyontheNumber→
NoBest,Worst,AverageCases.
•LetC(n)denotethenumberoftimestheMultiplicationoperation,Fact(n–1)*n,isexecuted.
n!=1*2*...*(n−1)*n=(n−1)!*nforn≥1and0!=1
Fact (n)=
??????&#3627408462;&#3627408464;&#3627408481;??????−1∗??????????????????(??????>0)
1 ????????????(??????=0)
C (n)=
1+????????????−1 ????????????(??????>0)
0 ????????????(??????=0)

25. Mathematical Analysis of NonrecursiveAlgorithms…
ЄΘ(n)
= C (n–1 –1) + 1= C (n–2) + 1
= C (n–2 –1) + 1= C (n–3) + 1
= C (n–1) + 1C (n)
= [C (n–2) + 1] + 1= C (n–2) + 1 + 1= C (n–2) + 2
= [C (n–3) + 1] + 2= C (n–3) + 1 + 2= C (n–3) + 3
= C (n–3 –1) + 1= C (n–4) + 1
= [C (n–4) + 1] + 3= C (n–4) + 1 + 3= C (n–4) + 4
.
.
.
After isteps
= C (n–i) + iC (n)
C (n)=
????????????−1+1 ????????????(??????>0)
0 ????????????(??????=0)
When i= n
C (n –1)= C [(n–1) –1] + 1
= C (n–n) + nC (n)
= C (0) + n
= 0 + n
= n
C (n –2)= C [(n–2) –1] + 1
C (n –3)= C [(n–3) –1] + 1
→ n–i= 0C (0) = 0⸫C (n–i) = 0 → i= n

26. Mathematical Analysis of Recursive Algorithms…
Example 2:Tower of Hanoi
AlgorithmToH(Src,Dest,Aux,n)
if (n =1)
Moven
th
Disk from Srcto Dest
else
ToH(Src, Aux, Dest, n–1)
Moven
th
disk from Srcto Dest
ToH(Aux, Dest, Src, n–1)
•InputSize
•BasicOperation
:NumberofDisks,n
:DiskMoveOperation.
•NumberoftimestheDiskMoveoperationisexecuteddependsonlyontheNumberofDisks
→NoBest,Worst,AverageCases.
•LetC(n)denotethenumberoftimestheDiskMoveoperationisexecuted.
C (n)=
????????????−1+1+????????????−1????????????(??????>1)
1 ????????????(??????=1)

27. Mathematical Analysis of NonrecursiveAlgorithms…
ЄΘ(2
n
)
= 2 C (n–1 –1) + 1= 2 C (n–2) + 1
= C (n–1) + C (n–1) + 1C (n)
= 2[2C (n–2) + 1] + 1
.
.
.
After isteps
C (n)
C (n)=
2????????????−1+1 ????????????(??????>1)
1 ????????????(??????=1)
When i= n –1
C (n –1)= 2 C [(n–1) –1] + 1
C (n)
→ n–i= 1C (1) = 1⸫C (n–i) = 1 → i= n –1
= 2C (n–1) + 1
= 2
2
C (n–2) + 2+ 1
= 2 C (n–2 –1) + 1= 2 C (n–3) + 1C (n –2)= 2 C [(n–2) –1] + 1
= 2
2
[2C (n–3) + 1] + 2 + 1= 2
3
C (n–3) + 2
2
+ 2+ 1
= 2 C (n–3–1) + 1= 2 C (n–4) + 1C (n –3)= 2 C [(n–3) –1] + 1
= 2
3
[2C (n–4) + 1] + 2
2
+ 2 +1= 2
4
C (n–4) + 2
3
+ 2
2
+ 2+ 1= 2
4
C (n–4) + 2
3
+ 2
2
+ 2
1
+ 2
0
= 2
i
C (n–i) + 2
i -1
+ . . . + 2
3
+ 2
2
+ 2
1
+ 2
0
= 2
n –1
C (n–(n–1)) + 2
(n –1) -1
+ . . . + 2
3
+ 2
2
+ 2
1
+ 2
0
= 2
n –1
C (n–n+ 1)) + 2
n –1 –1
+ . . . + 2
3
+ 2
2
+ 2
1
+ 2
0
= 2
n –1
C (1) + 2
n –2
+ . . . + 2
3
+ 2
2
+ 2
1
+ 2
0
= 2
n –1
*1 + 2
n –2
+ . . . + 2
3
+ 2
2
+ 2
1
+ 2
0
= 2
n –1
+ 2
n –2
+ . . . + 2
3
+ 2
2
+ 2
1
+ 2
0
= 2
(n –1) + 1
–1 = 2
n –1 + 1
–1 = 2
n
–1 ≈2
n

28. Mathematical Analysis of Recursive Algorithms…
Example 3:Number of binary digits in the binary representation of a positive decimal integer.
AlgorithmBinRec(n)
if (n =1)
return1
else
return BinRec
n
2
+1
•InputSize
•BasicOperation
:Number,n
:DivisionOperation,BinRec
n
2
+1
•NumberoftimestheDivisionoperationisexecuteddependsonlyontheNumberofBitsinthe
BinaryRepresentationonn→NoBest,Worst,AverageCases.
•LetC(n)denotethenumberoftimestheDivisionoperationisexecuted.
C (n)=
1+??????
n
2
????????????(??????>1)
0 ????????????(??????=1)

29. Mathematical Analysis of NonrecursiveAlgorithms…
ЄΘ(log
2n)
= C
n
2
+ 1
⸫C (2
k
)
Let n= 2
k
.
After isteps
C (2
k
)
C (n)=
??????
n
2
+1 ????????????(??????>1)
0 ????????????(??????=1)
When i= k
C (2
k–1
) = C (2
k–2
) + 1
→ 2
k–i
= 1 → k –i= 0
= C
2
k
2
+ 1
C (n)
= C 2
k–1
+ 1
= [C 2
k–2
+ 1]+ 1= C 2
k–2
+ 1 + 1= C 2
k–2
+ 2
= C (2
(k–1)–1
) + 1= C (2
(k–1–1
) + 1
C (2
k–2
) = C (2
k–3
) + 1= C (2
(k–2)–1
) + 1= C (2
(k–2–1
) + 1
= [C 2
k–3
+ 1]+ 2= C 2
k–3
+ 1 + 2= C 2
k–3
+ 3 C (2
k–3
) = C (2
k–4
) + 1= C (2
(k–3)–1
) + 1= C (2
(k–3–1
) + 1
= [C 2
k–4
+ 1]+ 3= C 2
k–4
+ 1 + 3= C 2
k–4
+ 4
.
.
= C 2
k–??????
+ i
C (1) = 0⸫C (2
k–i
) = 0 2
0
= 1
⸫i= k
= C 2
k–k
+ k = C 2
0
+ k = C 1+ k = 0+ k = k
Since n= 2
k
,We have, k = log
2n
= log
2n⸫C (n)

30. Mathematical Analysis of Recursive Algorithms…
Example 3:Finding the n
th
Fibonacci Number.
Fibonacci Numbers –Introduced by Leonardo Fibonacci (1202)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. . .
Explicit Formula for the n
th
Fibonacci Number, Fib (n):
Fib (n)= Fib (n–1)+ Fib (n–2)
Fib (n) –Fib (n–1) –Fib (n–2) = 0
(Homogeneous Second-Order Linear Recurrence with Constant Coefficients)
Characteristic Equation:r
2
–r–1 = 0(Quadratic Equation)
Fib (n)=
????????????&#3627408463;??????−1+????????????&#3627408463;(??????−2)????????????(??????>1)
0 ????????????(??????=0)
1 ????????????(??????=1)
→(2)
→(1)

31. Mathematical Analysis of Recursive Algorithms…
Roots of the Characteristic Equation:
r=
−&#3627408463;±&#3627408463;
2
−4&#3627408462;&#3627408464;
2&#3627408462;
a= 1, b= –1, c= –1
=
−(−1)±−1
2
−41(−1)
2(1)
=
1±1+4
2
Fib(n) = &#3627409148;??????
1
??????
+&#3627409149;??????
2
??????
&#3627409148;,&#3627409149;–Arbitrary Real Constants
→(3)
→(4)
→??????
1=
1+5
2
andr
2=
1−5
2
=
1±5
2
→The general solution to the recurrence (2)is given by:Roots are real and distinct
r
2
–r–1 = 0
Fib (n) –Fib (n–1) –Fib (n–2) = 0

32. Mathematical Analysis of Recursive Algorithms…
Substituting r
1and r
2from (3)in (4)
Fib(n)= &#3627409148;
1+5
2
??????
+&#3627409149;
1−5
2
??????
Fib (0) = 0, From (1)
⸫Substituting n= 0 in (5)
Fib (0) =&#3627409148;
1+5
2
0
+&#3627409149;
1−5
2
0
i.e., 0 = &#3627409148;+&#3627409149;
Also, Fib (1) = 1, From (1)
⸫Substituting n= 1 in (5)
Fib (1)= &#3627409148;
1+5
2
1
+&#3627409149;
1−5
2
1
→(5)
→(6)
i.e., 1= &#3627409148;
1+5
2
+&#3627409149;
1−5
2
(6)→&#3627409149;= –&#3627409148;
Substituting (8)in (7)
1= &#3627409148;
1+5
2
+(−&#3627409148;)
1−5
2
1= &#3627409148;
1+5
2
−&#3627409148;
1−5
2
1 =
??????+??????5
2
−
??????−??????5
2
1=
??????+??????5−(??????−??????5)
2
1=
??????+??????5−??????+??????5)
2
1=
2??????5)
2
→(7)
→(8)

33. Mathematical Analysis of Recursive Algorithms…
1= &#3627409148;5
&#3627409148;=
1
5
Substituting (9)in (8)
&#3627409149;= –
1
5
Substituting (9)and (10)in (5)
Fib(n) =
1
5
1+5
2
??????
–
1
5
1−5
2
??????
∅(Golden Ratio) =
1+5
2
≈1.61803and ∅
??????
= –
1
∅
≈–0.61803
→(9)
→(10)
ЄΘ(∅
??????
)
→(11)=
1
5
(∅
??????
– ∅
??????
)=
1
5
∅
??????
–
1
5
∅
??????
≈(∅
??????
)

34. Mathematical Analysis of Recursive Algorithms…
Algorithm to Find n
th
Fibonacci Number using the Recurrence in (1):
Fib (n)=
????????????&#3627408463;??????−1+????????????&#3627408463;(??????−2)????????????(??????>1)
0 ????????????(??????=0)
1 ????????????(??????=1)
AlgorithmFib(n)
if (n ≤1)
returnn
else
return (Fib (n–1) +Fib (n–2))
•InputSize
•BasicOperation
:Number,n
:AdditionOperation
Fib(n–1)+Fib(n–2)
•NumberoftimestheAdditionoperationis
executeddependsonlyontheNumbern→
NoBest,Worst,AverageCases.
•LetC(n)denotethenumberoftimestheAddition
operationisexecuted.

35. C (n) =C (n–1) +C (n–2) +1
C (n) –C (n–1) –C (n–2) =1
(12)is similar to (2) but RHS is equal to 1
(12)Can be reduced to a Homogeneous equation by addingand subtracting1
C (n) –C (n–1) –C (n–2) +1 –1 –1 =0
C (n) +1 –C (n–1) –1 –C (n–2) –1 =0
(C (n) + 1)–(C (n–1) +1)–(C (n–2) +1)=0
Mathematical Analysis of Recursive Algorithms…
C (n)=
????????????−1+1+????????????−2????????????(??????>1)
0 ????????????(??????=0)
0 ????????????(??????=1)
→Inhomogeneous→(12)
→(13)

36. Mathematical Analysis of Recursive Algorithms…
Let, A (n) =C (n) + 1
(14)→A (n –1) =C (n–1) + 1,A (n –2) =C (n –2) + 1,A (0) =1 andA (1) =1→(15)
Substituting (14) and (15)in (13):
A (n) –A (n –1) –A (n –2) = 0
Hence,therecurrence:
Recurrence (16) is similar to recurrence (1)except that it starts with two 1s and hence
A (n) is one step ahead of Fib (n).
i.e., A (n) = Fib (n+ 1) =
1
5
(∅
??????+1
– ∅
??????+1
) (⸪Fib (n)=
1
5
(∅
??????
– ∅
??????
) from (11))
(14)→C (n) = A (n) –1
⸫C (n) =
1
5
(∅
??????+1
– ∅
??????+1
) –1
A (n)=
????????????−1+????????????−2 ????????????(??????>1)
1 ????????????(??????=0)
1 ????????????(??????=1)
→(16)
→(14)
ЄΘ(∅
??????
)≈(∅
??????
)

37. Mathematical Analysis of Recursive Algorithms…
Tree of Recursive calls for computing 5
th
Fibonacci Number
Drawback:
Poor Efficiency

38. Mathematical Analysis of Recursive Algorithms…
Alternate Solutions:
1.Iterative Algorithm
Efficiency-Linear
AlgorithmFib(n)
F(0)=0
F(1)=1
for (i=2 to n)do
F [i] ←F[i–1]+F[i–2]
return (F [n])
3.Algorithm based on Matrix
Efficiency-Determinedbytheefficiencyof
thealgorithmcomputingMatrixPowers.
2.Algorithm using the Formula
Efficiency-Determinedbytheefficiency
ofanExponentiationAlgorithmusedfor
computing∅
??????

39. Empirical Analysis of Algorithms
Drawback of Mathematical Analysis:
•VerydifficulttoAnalyzeevensomeseeminglysimplealgorithmswith
MathematicalPrecisionandCertainty.
General Plan for the Empirical Analysis of Algorithm Time Efficiency
1.Understandtheexperiment’spurpose.
2.DecideontheEfficiencyMetricMtobemeasuredandtheMeasurementUnit.
3.DecideonCharacteristicsoftheInputSample.
4.PrepareaProgramimplementingthealgorithm(s)fortheexperimentation.
5.GenerateaSampleofInputs.
6.Runthealgorithm(s)onthesample’sinputsandRecordtheDataobserved.
7.AnalysetheDataobtained.

40. Empirical Analysis of Algorithms…
1.Goals in Analyzing Algorithms Empirically:
•CheckingtheAccuracyofaTheoreticalAssertionaboutalgorithm’sefficiency.
•ComparingtheEfficiencyofseveralalgorithmsforsolvingthesameproblemor
differentimplementationsofthesamealgorithm.
•DevelopingaHypothesisaboutthealgorithm’sefficiencyclass.
•AscertainingtheEfficiencyoftheprogramimplementingthealgorithmona
particularMachine.
2.EfficiencyMetrictobeMeasured:
i.InsertaCounter(orcounters)intoaprogramimplementingthealgorithmto
countthenumberoftimesthealgorithm’sbasicoperationisexecuted.
ii.Timetheprogramimplementingthealgorithminquestion:
a)UseaSystemCommand.Eg.:timecommandinUNIX.
b)AskfortheSystemTimerightbeforetheprogramfragment’sstart(t
start)andjust
afteritscompletion(t
finish),andthencomputethedifferencebetweenthetwo
(t
finish−t
start).Eg.:ClockfunctioninCandC++.

41. Empirical Analysis of Algorithms…
Drawbacks:
System’stimeistypicallyNotveryAccurateandthereisapossibilityofgettingDifferent
ResultsonRepeatedRunsofthesameprogramonthesameinput.
Solution:
MakeseveralsuchMeasurementsandthentaketheirAverage(orthemedian).
Duetothehighspeedofmoderncomputers,therunningtimemayFailtoRegisteratall
andbereportedaszero
Solution:
Runtheprograminanextraloopmanytimes,measurethetotalrunningtime,and
thendivideitbythenumberoftheloop’srepetitions.
Atime-sharingsystemmayincludethetimespentbytheCPUonotherprograms.
Solution:
UsesuitableCommandtorequestthesystemtoprovidetimedevotedspecificallyto
executionoftheprogram.
Advantages:
ProvidesveryspecificInformationaboutanalgorithm’sperformanceinaparticular
ComputingEnvironment.

42. Empirical Analysis of Algorithms…
Profiling-Measuringtimespentondifferentsegmentsofaprogramcanpinpointa
Bottleneckintheprogram’sperformancethatcanbemissedbyanabstractdeliberationabout
thealgorithm’sbasicoperation.
3.CharacteristicofInputSamples:
•Goalistouseasamplerepresentinga“typical”input.
SetofinstancesdevelopedbyResearchersforBenchmarking.Eg.:TSP.
HastobedevelopedbytheExperimenter.
•SampleSize–Sensibletostartwitharelativelysmallsampleandincreaseitlaterif
necessary.
•RangeofInstanceSizes–Typicallyneithertriviallysmallnorexcessivelylarge.
AdheretosomePattern.e.g.,1000,2000,3000,...,10,000.
Advantage:
ImpactisEasiertoAnalyze.Eg.:Ifasample’ssizesaregeneratedbydoubling,theratios
M(2n)/M(n)canbecomputedtoseewhethertheratiosexhibitabehaviortypicalof
algorithmsinoneofthebasicefficiencyclasses.
Drawback:
Thealgorithmunderinvestigationmayexhibitatypicalbehavioronthesamplechosen.

43. Empirical Analysis of Algorithms…
Eg.:Ifallthesizesinasampleareevenandthealgorithmrunsmuchmoreslowlyonoddsize
inputs,theempiricalresultswillbequitemisleading.
GenerateRandomlywithintherangechosen.
Iftheobservedmetricisexpectedtovaryconsiderablyoninstancesofthesamesize,include
severalinstancesforeverysizeinthesample.
ComputeAveragesorMediansoftheobservedvaluesforeachsizeandinvestigateinsteadoforin
additiontoindividualsamplepoints.
5.GenerateaSampleofInputs:
InstancescanbegeneratedrandomlyusingProcedureslike:
RandomNumberGeneratorsavailableincomputerlanguagelibraries
Producea(pseudo)randomvariableuniformlydistributedintheintervalbetween0and1.
Ifadifferent(pseudo)randomvariableisdesired,anappropriatetransformationneedstobemade.
ImplementingoneofseveralknownAlgorithms.Eg.:LinearCongruentialMethod.
Note:Random numbers generated on a digital computer can be Solvedonly Approximately.
Hence computer scientists call such numbers Pseudorandom.

44. Empirical Analysis of Algorithms…
Recommendationsforchoosingthealgorithm’s
parametersbasedontheresultsofa
sophisticatedmathematicalanalysis.
seed –May be chosen Arbitrarily.
Often set to the Current Date and Time.
m –Should be Large.
Taken as 2
w
. w –Computer Word’s Size.
a –Integerbetween 0.01mand 0.99mwith
no particular pattern in its digits but
such that amod 8 = 5.
b –1.
AlgorithmRandom(n,m,seed,a,b)
r
0←seed
for (i=1 to n)do
r
i←(a* r
i–1+b)mod m
•GeneratesaSequenceofn
PseudorandomNumbersaccordingto
thelinearcongruentialmethod.
•Input:Apositiveintegernandpositive
integerparametersm,seed,a,b.
•Output:Asequencer
1,...,r
nofn
pseudorandomintegersuniformly
distributedamongintegervalues
between0andm−1.

45. Empirical Analysis of Algorithms…
6.RecordthedataobservedandAnalyze:
•The empirical data obtained can be Presentedas:
Table
CanbeManipulatedEasily.Eg.:RatiossuchasM(n)/g(n)orM(2n)/M(n)canbe
computed.g(n)–candidaterepresentingtheefficiencyclassofthealgorithmin
question.
Scatterplot–PointsinCartesianCoordinateSystem.
Mayalsohelpinascertainingthealgorithm’sProbableEfficiencyClass.
LinearLogarithmic
Logarithmic Algorithm
Will have a Concaveshape
Linear Algorithm
Points tend to
(1)Aggregate around a Straight Line
(2)Contained between 2 Straight Lines

46. Empirical Analysis of Algorithms…
One of the Convex Functions
??????(nlog n), n
2
, n
3
etchave convex shape.
Applicationof the empirical analysis –Extrapolation
(Predictingthe algorithm’s performanceon an instance not included in the experiment sample).
Eg.: If the ratios M(n) / g(n) are observed to be close to some constant c, it could be sensible to approximate
M(n) by the product cg(n) for other instances, too.
Mathematical Analysis Empirical Analysis
StrengthsIndependenceof Specific Inputs Applicableto any algorithm
WeaknessLimited Applicability especially for
investigatingAverage-case efficiency.
Resultscan dependon the particular Sample
of instances and the Computerused in the experiment.

47. Algorithm Visualization
•ThirdwayofStudyingAlgorithmsotherthanmathematicalandempiricalanalyses.
•DefinedastheuseofImagestoconveysomeusefulinformationaboutalgorithms.
TheinformationcanbeaVisualIllustrationof:
AnAlgorithm’sOperation.
ItsPerformanceondifferentkindsofinputs.
ItsExecutionSpeedversusthatofotheralgorithmsforthesameproblem.
•ItusesGraphicElementslikePoints,LineSegments,Two-orThree-dimensional
Bars,etc.
VariationsofAlgorithmVisualization
1.StaticAlgorithmVisualization
Showsanalgorithm’sprogressthroughaseriesofStillImages.
2.DynamicAlgorithmVisualization(AlgorithmAnimation)
Showsacontinuous,Movie-likePresentationofanalgorithm’soperations.
MoreSophisticatedoptionbutmoredifficulttoimplement.

48. Algorithm Visualization…
HistoryofAlgorithmVisualizaion:
•Effortsinstartedin1971.
•SortingoutSorting(1981)
30-minutecolorsoundfilmcontainingVisualizationsofNinewell-known
sortingalgorithms.
ProducedattheUniversityofTorontobyRonaldBaeckerwiththeassistanceof
D.Sherman.
ProvidedquiteaconvincingdemonstrationoftheRelativeSpeeds.

49. Algorithm Visualization…
•SortingproblemlendsitselfquiteNaturallytovisualpresentationviaverticalor
horizontalbarsorsticksofdifferentheightsorlengths,whichneedtobe
rearrangedaccordingtotheirsizes.
•Convenientbutsuitableonlyforsmallinputs.

50. Algorithm Visualization…
•ForLargeFiles,Scatterplotcanbeusedwiththefirstcoordinaterepresentingan
item’spositioninthefileandthesecondonerepresentingtheitem’svalue.
•Theprocessofsortinglookslikeatransformationofa“random”scatterplotof
pointsintothepointsalongaframe’sdiagonal.

51. Algorithm Visualization…
•MostSortingAlgorithmsworkbycomparingandexchangingtwoitemswhichcan
beAnimatedEasily.
•GreatnumberofalgorithmAnimationshavebeencreatedaftertheappearanceof
JavaandtheWorldWideWebinthe1990s.
•Attheendof2010,acatalogoflinkstoexistingvisualizations,maintainedunder
theNSF-supportedAlgoVizProject,containedover500links.
ApplicationsofAlgorithmVisualization:
1.Research
MayhelpUncoversomeUnknownFeaturesofalgorithms.
Eg.:(1)VisualizationoftherecursiveTowerofHanoialgorithminwhichodd-
andeven-numbereddiskswerecoloredintwodifferentcolorsshowed
thattwodisksofthesamecolornevercameindirectcontactduring
thealgorithm’sexecution.Thisobservationhelpedindevelopinga
betternon-recursiveversionoftheclassicalgorithm.

52. Algorithm Visualization…
(2)UsinganalgorithmanimationsystemhelpedBentleyandMcIlroyon
ImprovingaLibraryImplementationofaleadingsortingalgorithm.
2.Education
SeekstohelpstudentsLearningalgorithms.
AvailableevidenceofitsEffectivenessisdecisivelymixed.
EvidenceindicatesthatcreatingsophisticatedsoftwaresystemsisNotgoingto
beEnoughasthelevelofstudentInvolvementwithvisualizationmightbe
moreImportantthanspecificfeaturesofvisualizationsoftware.
Insomeexperiments,Low-techVisualizationspreparedbystudentsweremore
Effectivethanpassiveexposuretosophisticatedsoftwaresystems.
Note:
•Successof algorithm visualization is Notas Impressiveas one might expect.
•A deeper understanding of Human Perception of Imageswill be required before the
true potential of algorithm visualization is fulfilled.

53. Appendix

&#3627408470;=&#3627408473;
??????
1=&#3627408482;−??????+1•

&#3627408470;=0
&#3627408475;
??????=•
&#3627408470;=1
&#3627408475;
??????=1+2+3+...+??????=
??????(??????+1)
2

&#3627408470;=&#3627408473;
??????
&#3627408464;&#3627408462;??????=• &#3627408464;
&#3627408470;=&#3627408473;
??????
&#3627408462;??????

&#3627408470;=0
&#3627408475;
2
??????
=
• 2
n + 1
−1

54. References:
•AnanyLevitin,IntroductiontotheDesignandAnalysisofAlgorithms,3
rd
Edition,
2012,PearsonEducation.
•DineshPMehtaandSartajSahni,HandbookofDataStructuresandApplications,
2005Chapman&Hall/CRC.