---
title: worst-case complexity
slug: worst-case-complexity
qid: Q8037118
snapshot: worst-case-complexity-904851-f3f400b986177be3
content_hash: f3f400b986177be37642c2636447acaea2e10823294fae59b895c38f0b5f0896
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1174886428
tags: [23118434, 23603337, 29176158]
---

# worst-case complexity

> [!note] Provenance
> Snapshot `worst-case-complexity-904851-f3f400b986177be3` · content root `f3f400b986177be3…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1174886428> · Licensed CC BY-SA 4.0

In computer science (specifically computational complexity theory), the worst-case complexity measures the resources (e.g. running time, memory) that an algorithm requires given an input of arbitrary size (commonly denoted as in asymptotic notation). It gives an upper bound on the resources required by the algorithm. In the case of running time, the worst-case time complexity indicates the longest running time performed by an algorithm given any input of size , and thus guarantees that the algorithm will finish in the indicated period of time. The order of growth (e.g. linear, logarithmic) of the worst-case complexity is commonly used to compare the efficiency of two algorithms. The worst-case complexity of an algorithm should be contrasted with its average-case complexity, which is an average measure of the amount of resources the algorithm uses on a random input.

In computer science (specifically computational complexity theory), the worst-case complexity measures the resources (e.g. running time, memory) that an algorithm requires given an input of arbitrary size (commonly denoted as in asymptotic notation). It gives an upper bound on the resources required by the algorithm. In the case of running time, the worst-case time complexity indicates the longest running time performed by an algorithm given any input of size , and thus guarantees that the algorithm will finish in the indicated period of time. The order of growth (e.g. linear, logarithmic) of the worst-case complexity is commonly used to compare the efficiency of two algorithms. The worst-case complexity of an algorithm should be contrasted with its average-case complexity, which is an average measure of the amount of resources the algorithm uses on a random input. t_{\mathsf{A}}(n) := \max_{s\in \{0, 1\}^n} t_{\mathsf{A}}(s) of inputs s with length or size \le n . Similar definitions can be given for space complexity, randomness complexity, etc. Very frequently, the complexity t_{\mathsf{A}} of an algorithm \mathsf{A} is given in asymptotic Big-O Notation, which gives its growth rate in the form t_{\mathsf{A}} = O(g(n)) with a certain real valued comparison function g(n) and the meaning: There exists a positive real number M and a natural number n_0 such that |t_{\mathsf{A}}(n)| \le M g(n) \quad \text{ for all } n\ge n_0. Quite frequently, the wording is: „Algorithm \mathsf{A} has the worst-case complexity O(g(n)) .“ or even only: „Algorithm \mathsf{A} has complexity O(g(n)) .“
