Measuring Efficiency: Big O and Arrays

Big O notation is the standard language computer scientists use to describe how the running time or memory usage of an algorithm grows as the size of its input, usually denoted n, increases. Rather than counting exact operations, which would depend on the specific hardware, compiler, or programming language, Big O focuses on the dominant term of that growth and discards constant factors and lower-order terms, since these become negligible as n grows very large. Common complexity classes, ordered from fastest to slowest growth, include constant time O(1), logarithmic time O(log n), linear time O(n), linearithmic time O(n log n), quadratic time O(n^2), exponential time O(2^n), and factorial time O(n!). This abstraction allows algorithms to be compared on equal footing and lets engineers predict how a program will behave as datasets scale from hundreds to millions of records.