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

so well came from computer science research that invented replacements for O( n !)
algorithms.
The term sub-linear refers to anything that grows less than linearly, such as constant and
logarithmic scaling. Super-linear refers to anything that grows faster, such as exponential
and factorial scaling.
In addition to being used to describe scaling, these terms are often used to describe
growth. One might describe the increase in customers being attracted to your business as
growinglinearly orexponentially.Therun-timeofasystemmightbedescribedasgrowing
in similar terms.
Super-linear systems sound awful compared to sub-linear systems. Why not always use
algorithms that are constant or linear? The simplest reason is that often algorithms of that
orderdon'texist. Sortingalgorithms havetotoucheveryitem atleast once,eliminating the
possibilityofO(1)algorithms.ThereisoneO( n )sortalgorithmbutitworksononlycertain
kinds of data.
Another reason is that faster algorithms often require additional work ahead of time:
for example, building an index makes future searches faster but requires the overhead and
complexity of building and maintaining the index. That effort of developing, testing, and
maintaining such indexing code may not be worth it if the system's performance is suffi-
cient as is.
At small values, systems of different order may be equivalent. What's bigger, x or x 2 ?
Yourgutreactionmaybethatthesquareofsomethingwillbebiggerthantheoriginalnum-
ber. However, if x is 0.5, then this is not true. 0.5 2 = 0.25, which is smaller than 0.5. Like-
wise, an O( n )algorithm may be slower than an O( n 2 )algorithm forvery small inputs. Also
an O( n 2 ) algorithm may be the easiest to implement, even though it wouldn't be the most
efficient for larger-sized input. Thus the more complex algorithm would be a waste of time
to develop. It would also be riskier. More complex code is more likely to have bugs.
Itisimportant toremember thattheconcept ofO()isagrossgeneralization thatfocuses
onthetrendasitsinputgrows,notthespecificrun-time.Forexample,twosystemsthatare
both O( n 2 ) will not to have the exact same performance. The shared order simply indicates
that both scale worse than, say, an O( n ) system.
O() notation is an indicator of the biggest factor, not all factors. A real system may be
dominated by an O( n ) lookup, but might also involve many O(1) operations and possibly
even some O( n 2 ) operations, albeit ones that are inconsequential for other reasons.
For example, an API call might perform an O( n ) lookup on a small list of authorized
users and then spend the majority of its time doing an O(1) lookup in a large database. If