Comparing algorithms of dissimilar performance order, such as
O(nlogn) for STL sort and O(kn) for Radix-Sort, should provide
insight about when one algorithm is expected to be better than
another. The comparison is easier to see if the orders are put
in a similar form, such as O(log2(n)*n) and O(k*n). Both
formulas have an n term in common, and thus the comparison is
between log2(n) and k . Another way to see this is to divide the
two formulas. In this case, n cancels out and log2(n)/k ratio
remains. If log2(n) is bigger than k, the ratio will be bigger
than 1. If k is bigger, the ratio will be less than 1. Table 8
demonstrates this relationship. It shows that log2(n) increases
by one when n doubles -- which follows from one of the rules of
logarithms, where log( m*n ) = log(m) + log(n). In this case,
log2( 2*n ) = log2(2) + log2(n) = 1 + log2(n). The second
portion of the table shows that for log2(n)to double, n has to
square, which follows from another rule of logarithms, where
m*log(n) = log(nm), where m=2