Please enable JavaScript.
Coggle requires JavaScript to display documents.
M4 (The default framewok, Asynptotic Notations, Analyzing Efficiency,…
M4
-
-
Analyzing Efficiency
Nonrecursive
- 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.
- Identify the algorithm’s basic operation. (As a rule, it is located in the innermost loop.)
- 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.
- Decide on a parameter (or parameters) indicating an input’s size.
Recursive
- Check whether the number of times the basic operation is executed can vary
on different inputs of the same size; if it can, the worst case, average case, and best-case efficiencies must be investigated separately
- Set up a recurrence relation, with an appropriate initial condition, for the
number of times the basic operation is executed.
- Identify the algorithm’s basic operation.
- Solve the recurrence or, at least, ascertain the order of growth of its solution
- Decide on a parameter (or parameters) indicating an input’s size.
Empirical Analysis
- 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
observed.
- Analyze the data obtained.