Source code online books for professionals by professionals

2
T (n )
n
0
Figure 2-1.  For values of n greater than n
0
, T(n) is less than cn
2
, so T(n) is O(n
2
)

---

Chapter 2 
■
 the BasiCs
14
Rules of the Road
While the definitions of the asymptotic operators can be a bit tough to use directly, they actually lead to some of the 
simplest math ever. You can drop all multiplicative and additive constants, as well as all other “small parts” of your 
function, which simplifies things a lot.
As a first step in juggling these asymptotic expressions, let’s take a look at some typical asymptotic classes, or 
orders. Table 
2-1
 lists some of these, along with their names and some typical algorithms with these asymptotic 
running times, also sometimes called running-time complexities. (If your math is a little rusty, you could take a look at 
the sidebar “A Quick Math Refresher” later in the chapter.) An important feature of this table is that the complexities 
have been ordered so that each row dominates the previous one: If f is found higher in the table than g, then f is O(g).
5
Table 2-1.  Common Examples of Asymptotic Running Times