Which notation signifies linear scaling of cost with input size?

The notation that signifies linear scaling of cost with input size is O(n). This notation means that as the input size (n) increases, the time or space complexity will increase linearly. In practical terms, if you double the size of your input, you can expect the time or resource usage to also double. This linear relationship is straightforward and often ideal in algorithm design because it indicates that the algorithm will perform predictably regardless of the specific characteristics of the input within reasonable limits.

In contrast, logarithmic scaling (O(log n)) suggests that the cost grows much slower than the linear relationship, indicating that even as inputs grow large, the increase in resources used does not correlate linearly. Quadratic scaling (O(n^2)) represents a scenario where the cost grows at a rate proportional to the square of the input size, leading to much more significant increases in resource usage with larger inputs. O(nm) indicates a relationship where the cost is the product of two variables (n and m), leading to potentially more complex behaviors when scaling.

Therefore, O(n) distinctly captures the essence of linear scaling, highlighting a consistent and predictable relationship between input size and resource consumption.