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
Space efficiency
Amount of memory units required by the algorithm in addition to the space needed for its input and output
Time efficiency or time complexity
How fast an algorithm in question runs
Basic operation
Usually the most time-consuming operation in the algorithm’s innermost loop
T (n) ≈ copC(n)
The efficiency analysis framework ignores multiplicative constants and concentrates on the count’s order of growth to within a constant multiple for large-size inputs
Worst-Case, Best-Case, and Average-Case Efficiencies
Asymptotic Notations and Basic Efficiency Classes
“big oh”
A function t (n) is said to be in O(g(n)), denoted t (n) ∈ O(g(n)), if t (n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer n0
“big omega”
A function t (n) is said to be in (g(n)), denoted t (n) ∈ (g(n)), if t (n) is bounded below by some positive constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer n0
“big theta”
A function t (n) is said to be in (g(n)), denoted t (n) ∈ (g(n)), if t (n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constants c1 and c2 and some nonnegative integer n0
Mathematical Analysis of Nonrecursive Algorithms
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.
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.
Identify the algorithm’s basic operation. (As a rule, it is located in the innermost loop.)
Decide on a parameter (or parameters) indicating an input’s size.
Mathematical Analysis of Recursive Algorithms | EXAMPLE 1
Set up a recurrence relation, with an appropriate initial condition, for the
number of times the basic operation is executed
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.
Identify the algorithm’s basic operation
Decide on a parameter (or parameters) indicating an input’s size
Solve the recurrence or, at least, ascertain the order of growth of its solution.
Empirical Analysis of Algorithms
Prepare a program implementing the algorithm (or algorithms) for the experimentation.
Generate a sample of inputs
Decide on characteristics of the input sample (its range, size, and so on).
Run the algorithm (or algorithms) on the sample’s inputs and record the data
observed
Decide on the efficiency metric M to be measured and the measurement unit
(an operation count vs. a time unit).
Analyze the data obtained.
Understand the experiment’s purpose
Algorithm Visualization
Static algorithm visualization
Dynamic algorithm visualization, also called algorithm animation