Definition:Algorithm/Analysis/Complexity
Jump to navigation
Jump to search
Definition
The complexity of an algorithm is defined as the number of discrete steps needed to terminate as a function of the number of inputs.
 | This page has been identified as a candidate for refactoring of advanced complexity. In particular: The below needs to be restructured and rethought Until this has been finished, please leave {{Refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code. |
 | This page or section has statements made on it that ought to be extracted and proved in a Theorem page. In particular: all the below You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by creating any appropriate Theorem pages that may be needed. To discuss this page in more detail, feel free to use the talk page. |
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
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): complexity (of an algorithm)
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): complexity (of an algorithm)
- 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