Scaling Terminology and Concepts - The Practice of Cloud System Administration - page 471

ing. A system that slows down at such a rate, if it interacts with all parts of our sys-
tem, would be a disaster! It might be fine if the input size is not expected to change
and, at the current size, the system is fast enough. This assumption carries a high
risk.
C.2 Big O Notation
O() or “ Big O notation ” is used to classify a system based on how it responds to changes
in input size. It is the more mathematical way of describing a system's behavior. O() nota-
tion comes from computer science. The letter “O” is used because the growth rate of an
algorithm's run-time is known as its “order.”
Here is a list of common Big O terms that a system administrator should be familiar
with. The first three we've already described:
• O(1): Constant Scaling: No change in performance no matter the size of the input.
• O( n ): Linear Scaling: Gets slower in proportion to the size of the input.
• O( n m ): Exponential Scaling: Performance worsens exponentially.
• O( n 2 ): Quadratic Scaling: Performance worsens relative to the square of the size
of input. Quadratic scaling is a special case of exponential scaling, where m is 2.
People tend to refer to systems as scaling “exponentially” when they actually mean
“quadratically.” This is so common that one rarely hears the term “quadratic” any-
more except when someone is being very specific (or pedantic) about the perform-
ance curve.
• O(log n ): Logarithmic Scaling: Performance worsens proportional to the log 2 of
the size of input. Performance asymptotically levels off as input size grows. For
example, a binary search grows slower as the size of the corpus being searched
grows, but less than linearly.
• O( n log n ): Loglinear Scaling: Performance worsens more than linearly, with the
“more than” component being proportional to log 2 of the size of input. Think of
this as linear scaling with a small but ever-growing performance surcharge added
as the input size grows. People often incorrectly use the term “logarithmic scaling”
when they actually mean “loglinear scaling.” You can use the term “loglinear”
when you want to sound like a true expert.
• O( n !): Factorial Scaling: Performance worsens proportional to the factorial of the
size of input. In other words, performance gets bad so quickly that each additional
unit of size worsens performance by a leap as big as all previous leaps put together
plus some more! O( n !) algorithms are usually a worst-case scenario. For example,
the breakthrough that permits Google PageRank and Facebook SocialRank to work