# 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 rethoughtUntil this has been finished, please leave
`{{Refactor}}` in the code.
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 belowYou 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**