Metraipolis › archive › dc_e6d59de71f70

Time complexity — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Time_complexity
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T14:06:28.592Z
SHA-256 of the archived text
08e9415f9fa149e2df73f48333e1d9975981285e22517d3fb97d7ff9b7f3fe41
Stable URL of this page
https://metraipolis.com/documento/dc_e6d59de71f70

How to cite

Time complexity — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Time_complexity (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_e6d59de71f70 (Metraipolis archive dc_e6d59de71f70, sha256 08e9415f9fa149e2df73f48333e1d9975981285e22517d3fb97d7ff9b7f3fe41)
BibTeX
@misc{dce6d59de71f70,
  title = {Time complexity — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Time_complexity},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_e6d59de71f70; sha256 08e9415f9fa149e2df73f48333e1d9975981285e22517d3fb97d7ff9b7f3fe41},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Time_complexity. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed as a function of the size of the input. Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behavior of the complexity when the input size increases—that is, the asymptotic behavior of the complexity. Therefore, the time complexity is commonly expressed using big O notation, typically O ( n ) {\displaystyle O(n)} , O ( n log n ) {\displaystyle O(n\log n)} , O ( n α ) {\displaystyle O(n^{\alpha })} , O ( 2 n ) {\displaystyle O(2^{n})} , etc., where n {\displaystyle n} is the size in units of bits needed to represent the input. Algorithmic complexities are classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexity O ( n ) {\displaystyle O(n)} is a linear time algorithm and an algorithm with time complexity O ( n α ) {\displaystyle O(n^{\alpha })} for some constant α > 0 {\displaystyle \alpha >0} is a polynomial time algorithm.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Time complexity» — https://en.wikipedia.org/wiki/Time_complexity
Wikidata Q2393193: «quantità di tempo impiegata da un algoritmo a essere eseguito» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2393193
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Time_complexity?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1375818064, consultata il 2026-10-06T12:26:06.731Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: d92540b90d772a09f186352af5e4f659c297763e108e1780cd1677a830cce833