Glossary: Data Structures and Algorithms in C++

Big-O notation

Also written: Big-O, O(1), O(n), O(n²), O(log n), O(n log n), O(V + E), constant time, linear time, logarithmic time, quadratic time

A way to describe how the number of steps grows as the input size n grows, ignoring constants and smaller terms. O(1) constant time is the same steps however big the data; O(log n) logarithmic time comes from halving the data each step; O(n) linear time grows in step with n; O(n²) quadratic time usually comes from a loop inside a loop.