Consider any mathematical function of T(n) = O(f(n)), which after n exceeds some value cf(n) will exceed the value of T(n) for some constant c. Does this really mean anything useful? I might say in a correct or logic way that n^{2} + 2n = O(n^{25}), though we don’t get a lot of information from that; n^{25} is simply too big.

While anyone use Big Oh analysis, there it can be chosen the function f(n) to be as small as possible and still satisfy the criteria of the definition of Big Oh. Thus, it is more meaningful to affirm that n^{2} + 2n = O(n^{2}); this tells us something about the growth pattern of the function n^{2} + 2n, namely that the n^{2} term will dominate the growth as n increases. The following functions are often encountered in computer science Big Oh analysis:

The growth patterns that follows have been listed in order of increasing “size.” That is,

O(1), O(lg(n)), O(n lg(n)), O(n^{2}), O(n^{3}), … , O(2^{n}).

- T(n) = O(1). This is called constant growth. T(n) does not grow at all as any function of n, it is a constant, which is pronounced as “Big Oh of one.” For instance, array access has this characteristic.
`A[i]`

takes the same time independent of the size of the array `A`

.
- T(n) = O(lg(n)). This is called logarithmic growth. T(n) grows proportional to the base 2 logarithm of n. Actually, the base doesn’t matter, it’s just traditional to use base-2 in computer science. Thus, it is pronounced “Big Oh of log n.” For instance, binary search has this characteristic.
- T(n) = O(n). This is called linear growth. T(n) grows linearly with n, which is pronounced “Big Oh of n.” For instance, looping all over the elements in a one-dimensional array would be an O(n) operation.
- T(n) = O(n log n). This is called “n log n” growth. T(n) grows proportional to n times the base 2 logarithm of n, which is pronounced “Big Oh of n log n.” For instance, Merge Sort has this characteristic. In fact, no sorting any algorithm that uses comparison between elements can be faster than n log n.
- T(n) = O(n
^{k}). This is called polynomial growth. T(n) grows proportional to the k-th power of n. We rarely consider algorithms that run in time O(n^{k}) where k is greater than 5, because such algorithms are very slow. For instance, selection sort is an O(n^{2}) algorithm. Thus, it is pronounced “Big Oh of n squared.”
- T(n) = O(2
^{n}) This is called exponential growth. T(n) grows exponentially, which is pronounced “Big Oh of 2 to the n.” Exponential growth is the most-feared growth pattern in computer science; algorithms that grow on this way are primordially useless for anything but very small problems.

Note that it is not true that if f(n) = O(g(n)) then g(n) = O(f(n)). The “=” sign does not mean equality in the usual algebraic sense—that’s why some people say “f(n) is *in* Big Oh of g(n)” and we never say “f(n) *equals* Big Oh of g(n).”

As always suppose that you have a choice of two approaches to writing a program. Both approaches have the same asymptotic performance (for example, both are O(n lg(n)). Why select one over the other, they’re both the same, right? They may not be the same.

Regarding that there is this small matter of the constant of proportionality. Suppose algorithms `A`

and `B`

have the same asymptotic performance, T_{A}(n) = T_{B}(n) = O(g(n)). Now suppose that `A`

does ten operations for each data item, but algorithm `B`

only does three. It is reasonable to expect `B`

to be faster than `A`

even though both have the same asymptotic performance. The reason is that asymptotic analysis ignores constants of proportionality.

As a quite specific example for this, let’s say that algorithm `A`

is

{ set up the algorithm, taking 50 time units; read in n elements into array A; /* 3 units per element */ for (i = 0; i < n; i++) { do operation1 on A[i]; /* takes 10 units */ do operation2 on A[i]; /* takes 5 units */ do operation3 on A[i]; /* takes 15 units */ } } Let’s now say that algorithm `B`

is

{ set up the algorithm, taking 200 time units; read in n elements into array A; /* 3 units per element */ for (i = 0; i < n; i++) { do operation1 on A[i]; /* takes 10 units */ do operation2 on A[i]; /* takes 5 units */ } }

Algorithm `A`

sets up faster than `B`

, but does more operations on the data. The execution time of `A`

and `B`

will be

T_{A}(n) = 50 + 3*n + (10 + 5 + 15)*n = 50 + 33*n

and

T_{B}(n) =200 + 3*n + (10 + 5)*n = 200 + 18*n

respectively. The following graph shows the execution time for the two algorithms as a function of n. Algorithm `A`

is the better choice for small values of n. For values of n > 10, algorithm `B`

is the better choice. Remember that both algorithms have time complexity O(n).

### Like this:

Like Loading...