What is the time complexity of a function whose cost scales linearly with the size of the input?

The time complexity of a function that scales linearly with the size of the input is represented as O(n). This notation indicates that as the input size n increases, the time taken by the function increases proportionally. In practical terms, if you were to double the size of the input, the time complexity would also roughly double, demonstrating a direct linear relationship.

When considering algorithms, a linear time complexity often occurs in scenarios such as iterating through an array or a list where every element must be examined exactly once. This is a common pattern in many data processing tasks, where efficiency is crucial, as the amount of data increases.

The other time complexities mentioned do not exhibit this linear scaling behavior: logarithmic complexity (O(log n)) reduces the number of operations dramatically with each additional input, quadratic complexity (O(n^2)) indicates a scenario where the operation count squares as input grows, and O(nm) suggests a dependence on two variables, leading to potentially more complex growth relative to single-dimensional data. Hence, O(n) correctly describes the linear relationship in the function's performance as input size changes.