# Time Complexity

> A measure of how an algorithm's running time grows as its input grows.

Record: `architecture:time-complexity`
Kind: metric
Layer: [Performance Core](https://banes-lab.com/records/layer/performance-core.md)
Severity: contextual
Scope: algorithm, function
Canonical: https://banes-lab.com/ontology#architecture-time-complexity

Listed in [Architecture principles](https://banes-lab.com/api/records/architecture.md), after [Algorithmic Efficiency](https://banes-lab.com/records/architecture/algorithmic-efficiency.md) and before [Space Complexity](https://banes-lab.com/records/architecture/space-complexity.md).

## Repair

- Refactored by: Improve Algorithm, Add Index/Cache
- Detected by: nested loops over large inputs, benchmark slope
- Violated by: unacceptable asymptotic runtime
- Measured by: Big O, runtime scaling
- Enforced by: benchmark thresholds

## Requires

- [Input Size Model](https://banes-lab.com/records/lexicon/input-size-model.md)

## Reinforces

- [Algorithmic Efficiency](https://banes-lab.com/records/architecture/algorithmic-efficiency.md)

## Enables

- [Scalability Analysis](https://banes-lab.com/records/lexicon/scalability-analysis.md)

## Conflicts with

- [Unbounded Runtime Growth](https://banes-lab.com/records/lexicon/unbounded-runtime-growth.md)

## In tension with

- [Space Complexity](https://banes-lab.com/records/architecture/space-complexity.md)

## Tensions

- [Time Complexity / Space Complexity](https://banes-lab.com/records/tension/space-complexity-time-complexity.md)

## Severity

- [contextual](https://banes-lab.com/records/vocabulary/severity-contextual.md)

## Category

- [Scalability / Performance / Optimization](https://banes-lab.com/records/architecture-category/scalability-performance-optimization.md)

## Linked from

- [Scalability / Performance / Optimization](https://banes-lab.com/ontology/principles/architecture-category-scalability-performance-optimization.md)
- [Scalability / Performance / Optimization](https://banes-lab.com/ontology/lexicon/lexicon-category-scalability-performance-optimization.md)
- [Severity levels](https://banes-lab.com/ontology/schema/the-vocabulary-severity.md)
- [The resolutions](https://banes-lab.com/ontology/schema/the-resolutions.md)