COT 3100 (Section #7094X), Fall 1999 Topic Review:
Orders of Growth

This topic was covered in lecture on Wed., Sep. 22. However, it is an important and somewhat difficult topic, and a single lecture does not really do it justice. Therefore I am providing these extra notes.

Motivation: Scaling Analysis

When designing hardware or software systems (computers, network protocols, or computer programs), some ever-present considerations are a system's performance, and its costs: How fast does the system operate, and how much raw computational resources (for example, processors, memory, or network bandwidth) are required for its operation?

Unfortunately, a design that performs well when the demands on the system are light may not perform so well when the demands increase. For example, a badly-designed database system might work fine for small data sets or infrequent usage patterns, but bog down and become ridiculously slow as more data is added or traffic increases. In this case we say that the system design does not scale well, as the task we are asking it to perform becomes more difficult.

A system's level of scalability tends to be very important in the real world, because the current enormous rate of growth of demand for computing (and of the economy in general) means that systems often end up being applied to tasks that are much more intensive than they were originally designed for. So it is important to design your computing products so that they scale well, and their performance degrades gracefully, or you may find that in a short time your customers start moving to a competitor's products, when they start bumping up against the limitations of your technology.

Some level of performance degradation might be unavoidable, due to the nature of the task being performed, and limitations on the computational resources (e.g., raw processing power and memory) that are available in the system.

However, often we find that a system's scalability to a large degree depends on specific choices in its design.

For example, in lecture we briefly outlined two different approaches for sorting (in increasing order) a list of data items. (For example, sorting account records by account number.) Sorting is a very commonly used operation throughout all information processing.

We saw that the "insertion sort" approach had the property that sorting a list of n items required a number of individual steps that scaled roughly in proportion to n2.

On the other hand, in the "quicksort" approach, the number of steps required scaled roughly in proportion to n log n.

Because of this difference in scaling, it turns out that independently of many details of how those procedures are implemented, for large enough lists, the quicksort approach will always turn out faster. This will be true even if the quicksort is run on a slow computer, and insertion sort on a fast computer. As the problem size n gets larger, the insertion sort gets slower and slower compared to the quicksort, and for large enough problems, the quicksort approach always wins out.

Now, suppose you are working for a computer or software company, and you are asked to design a system module that performs some task, such as sorting. If you pay attention to these issues of scalability, then you will be able to choose a design that will perform about as well as possible in all cases, and not just the easiest ones. Otherwise, your system may bog down as the data sizes increase, and people will curse your name.

Furthermore, if the assigned task happens not to just be some simple and already well-understood operation such as sorting, then in order to determine the best design for the job, you will have to analyze alternative designs yourself, to figure out which is better. If the task and the design alternatives are very complex, how will you approach this problem?

Hopefully, you will do it partly by using your understanding of the orders of growth of functions, which you will have gained from this class (and others).

Order of Growth Notation

Order of growth notation gives us a precisely-defined mathematical language and analytical tool that we can use to express how quantities scale compared to other quantities, and reason about these scaling relationships.

For any function (for example, a function that gives the running time of a sort routine as a function of the number of elements in the input data set), we define the order of growth of that function (or just order for short) as follows:

Definition 1: For any function f:, the order of f, written (f), is the set of all functions g such that g(x) falls between two constant multiples of f(x), for all sufficiently large values of x. Written formally:

(f) = { g: | k, c1, c2: x > k:
c1f(x) < g(x) < c2f(x) }
(The book gives a slightly different definition that involves taking the absolute values of f and g, but the difference between the two versions is usually not important, since typical functions that we use order of growth analysis on, such as program run times, are always positive.)

The order of f is an example of what is called an equivalence class of functions, meaning that it is a set of functions that are all considered the same in a certain respect. Specifically, all functions in (f) have order f, and no other functions do.

So, how do we use this "order" concept? In our sorting example, if we were to define T(n) as a function giving the running time of an insertion sort program on n inputs, then our earlier vague statement about the running time of insertion sort can now be stated more precisely as:

The order of T(n) is (n2).
Or, any of the following statements are equivalent ways of saying the same thing: Occasionally, you will see people abuse the notation, and write such a statement as:
T(n) = (n2).
but be on alert when you see that usage, because the equals sign in that statement does not really mean equality, rather, it is just a special shorthand for the statement that the given function is of the given order.

Simplifying the Order of a Function

Although one can correctly write the order of any function f as just (f), if we want to be able to tell what other functions have the same order as f, it helps to express the order of f in the simplest form that we can.

For example, the order of 3x2 is (3x2), by definition, but this is not the simplest way of writing this order. A simpler way to write the very same order is just (x2).

The reason that 3x2 has the same order as x2 is just that the two functions differ by only the constant factor 3, which can be accomodated by the constants c1 and c2 in definition 1 above. That is, 3x2 is between, for example, 2x2 and 4x2.

As another example, the function x2+1 also has order x2, because for all x > 1, we can show that x2+1 lies in between x2 and 2x2. So, you can see that additive as well as multiplicative constants are irrelevant when determining a function's order.

More generally, the order of any sum of functions with a fixed number of terms is just the order of the highest-order term. But to find the highest-order term, we need some concept that will let us determine which orders are "higher than" or "lower than" than each other.

Comparing Orders of Growth

The following two definitions let us say which orders of growth are higher or lower than others.

Definition 2. We say that a function g is at most order f, or g O(f), if g(x) is bounded above by a constant times f(x) for all sufficiently large x. Formally,

O(f) = { g: | k, c: x > k: g(x) < cf(x) }.
Definition 3. We say that a function g is at least order f, or g (f), if g(x) is bounded below by a constant times f(x) for all sufficiently large x. Formally,
(f) = { g: | k, c: x > k: g(x) > cf(x) }.
It is easy to verify that with these definitions, a function is order f if and only if it is at most order f and it is at least order f. Formally, (f) = O(f) (f).

Now, with these definitions, we can say some things about the relationships between functions having different orders of growth.

More to come...