Please enable JavaScript.
Coggle requires JavaScript to display documents.
Fundamentals of the Analysis of algorithm efficiency - Coggle Diagram
Fundamentals of the Analysis of algorithm efficiency
The Analysis Framework
Time Efficiency
time complexity
Space Efficiency
Space complexity
Measuting an inputs size
b = [log2 n] + 1
Units For measuring runiing time
Number of eexecutions
Worst Case
Best Case
Average Case
Asymptotic Notations And Basic Efficienty Classes
bit theta - notation
t (n) is bounded below by some positive constant multiple of g(n) for all large n
big omega - notation
f t (n) is bounded both above and below by some positive constant multiples of
g(n) for all large n
O-notation
t (n) is bounded above by some constant multiple of g(n) for all large n
computing the limit of the ratio of two functions in question
Mathematical Analysis of Nonrecursive Algorithms
Analysing the time efficiency
The worst case input is an array for which the number of element
comparisons Cworst(n) is the largest among all arrays of size n
General plano to analyze
Mathematical Analysis of Recursive Algoritms
Recursive algorithms
method of backward
substitutions
construct a tree of its recursive calls
Empritical Analysis of Algorithms
General plan to analyze
Data can be presented numerically in a table or
graphically in a scatterplot
Algoritmo gerando de numeros aleatorios
details of choosing the algorithm’s parameters
Example
Fibonacci numbers
Faster
homogeneous second-order linear recurrence with constant coefficients
inhomogeneous
