Definition:Algorithm/Analysis/Complexity
Jump to navigation
Jump to search
Definition
An algorithm may be analysed in the context of its complexity.
This is typically via measures of run-times using big-$\OO$, or big-$\Omega$, or $\Theta$ notation.
Complexity can be through 3 main types of analysis:
- Average-Case Analysis, using a distribution of cases to find an average case of the algorithm run-time for analysis
- Best-Case Analysis, using the best possible problem instance of the algorithm for analysis
- Worst-Case Analysis,using the worst possible problem instance of the algorithm for analysis
Sources
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): algorithmic complexity
- 2021: Richard Earl and James Nicholson: The Concise Oxford Dictionary of Mathematics (6th ed.) ... (previous) ... (next): algorithmic complexity