time complexity
A description of how the amount of work an algorithm does grows as its input gets bigger.
In more detail
Time complexity counts basic steps, such as comparisons or loop iterations, as a function of the input size n. It ignores the speed of the particular machine, because once two algorithms grow at different rates, the slower-growing one always wins for large enough input. It is usually written in Big O notation, such as O(n) or O(log n).
Example
Scanning a list of ten thousand users is O(n); looking one up in a dict is O(1).Related terms
- input size — The number, written n, that measures how big an input is, such as a list length, a row count or a string length.
- growth rate — The rule that says how fast an algorithm's cost rises as the input size n rises, such as constant, linear or quadratic.
- Big O notation — A way of writing an upper bound on growth: O(f(n)) means the cost grows no faster than a constant times f(n) for large n.
- space complexity — How the extra memory an algorithm needs grows with the input size, written in the same Big O notation as time.
- Dictionary<TKey, TValue> — The .NET collection that maps unique keys to values and finds a value by its key in constant time by hashing the key.
- List<T> — The .NET growable array: items keep their order, reading by index is constant time, and searching by value walks the whole list.
- HashSet<T> — The .NET collection of unique items that answers 'have I seen this one already?' in constant time.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers
- Collections, Generics, and LINQ — Modern .NET Core, C# & Enterprise Microservices