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
Mathematical Analysis of Nonrecursive Algorithms
:red_flag:
General Plan for Analyzing the Time Efficiency of Nonrecursive Algorithms
Decide on a parameter (or parameters) indicating an input’s size.
Identify the algorithm’s basic operation. (As a rule, it is located in the innermost loop.)
Check whether the number of times the basic operation is executed depends only on the size of an input. If it also depends on some additional property,the worst-case, average-case, and, if necessary, best-case efficiencies have to be investigated separately.
Set up a sum expressing the number of times the algorithm’s basic operation is executed.4
Using standard formulas and rules of sum manipulation, either find a closedform formula for the count or, at the very least, establish its order of growth
The Analysis Framework
Both time and space efficiencies are measured as functions of the algorithm’s
input size.
Time efficiency is measured by counting the number of times the algorithm’s
basic operation is executed.
Space efficiency is measured by counting the
number of extra memory units consumed by the algorithm.
The efficiencies of some algorithms may differ significantly for inputs of the
same size.
For such algorithms, we need to distinguish between the worst case,average-case, and best-case efficiencies.
Asymptotic Notations and Basic Efficiency Classes
Big O Notation: Mastery in defining the upper bound of an algorithm's time complexity,aiding in identifying the worst-case scenario.
Big Omega Notation: determining the lower bound of an algorithm's time complexity highlighting the best-case scenario.
Big Theta Notation: Ability to establish tight bounds on an algorithm's time complexity providing both upper and lower limits for precise analysis.
Empirical Analysis of Algorithms
General Plan for the Empirical Analysis of Algorithm Time Efficiency
Understand the experiment’s purpose.
Decide on the efficiency metric M to be measured and the measurement unit (an operation count vs. a time unit).
Decide on characteristics of the input sample (its range, size, and so on).
Prepare a program implementing the algorithm (or algorithms) for the experimentation.
Generate a sample of inputs.
Run the algorithm (or algorithms) on the sample’s inputs and record the data (an operation count vs. a time unit).
Analyze the data obtained