An Introduction to Rate of Growth
From StoneHome
The Idea
Contents |
Rate of growth is a central concern when programming. Expressed in various ways but most commonly through Big O notation, rate of growth is arguably the most important factor when selecting algorithms, containers, and other principal fundamental underpinnings of code. The concept of rate of growth is also the basis of calculus, and is fundamental to physics and biology, among other things.
The basic principle of rate of growth is to observe the way in which growth changes for a system. A common example is a trick most geometry teachers show their students, where a linear equation with a huge coefficient is compared to an quadratic equation with a small coefficient, and the students are asked to guess which equation will end up surpassing the other. For example, given the linear y=1000x and the quadratic y=2x2, many naïve students will compare 1000 to 2, and suspect the linear equation of growing fastest. Of course, this holds true for small values of x, but by x=500 the quadratic has caught up, and from there on in it wins. The reason this occurs is that the linear always grows by the same amount per tick, but the quadratic keeps growing by more each tick, so eventually it's growing by a larger factor than the linear, and inevitably surpasses it.
This is the basis of the concept of rate of growth: the observation that some rates of growth are steady (linear,) or changing (exponential, logarithmic, etc), or zero (constant,) et cetera. It is important to understand and be ready to apply these concepts, because they're critical in the selection of approaches to problems; your lookup, insert and delete, set, append, space consumed and so forth are frequently directly expressable in these terms.
Some examples
An easy beginning example is the C Array. Then, we'll look at a linked list and a map, and finally contrast the three. We will be measuring rates of growth in respect to the container's element count; the basis of the rate of growth measurement is traditionally written as N, so for these examples, N refers to the number of items in the container.
C Arrays
The C array can be described as having linear size, constant lookup, and linear insert and delete. Let's inspect why.
Constant Lookup
The C array has constant-effort lookup. In order to look up an entry in an array, you simply multiply the offset by the entry size and add the base pointer. This is always one add, one multiply and three variable lookups, regardless of the array's size; therefore, no matter the size of N, the lookup time does not change. We call the lookup time a constant, because it doesn't vary from those five actions.
Linear Insert and Delete
The C array has linear-effort insert and delete. This is because in order to resize a C array, a new array of the changed size must be allocated, and populated from the old array (without considering issues of realloc().) This means that the larger the array is, the more work it is to change its contents.
