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.
In more detail
Complexity arguments describe work as a function of n, so the first step is always to say what n counts. For a graph there are often two sizes, V vertices and E edges, and costs are written with both. When n doubles, a linear algorithm does about twice the work while a constant-time one does the same work.
Related terms
- time complexity — A description of how the amount of work an algorithm does grows as its input gets bigger.
- 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.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers