Growth of Functions and Efficency

A Quick Mathematical Review

Common Names:

If a function is O(log(n)) we call it logarithmic.
If a function is O(n) we call it linear.
If a function is O(n²) we call it quadratic.
If a function is O(n^k) with k≥1, we call it polynomial.
If a function is O(aⁿ) with a>1, we call it exponential.

Summations

Definition: The sigma (HTML) notation: ∑f(i) with i going from a to b.

Theorem: Assume 0<a≠1. Then ∑aⁱ with i going from 0 to n = (1-aⁿ⁺¹)/(1-a).
Proof: Multiply by a and subtract.

Theorem: ∑i with i going from 1 to n = n(n+1)/2.
Proof: Pair the 1 with the n, the 2 with the (n-1), etc. This gives n/2 values of (n+1)s.

Logarithms and Exponents

Recall that log_ba = c means that b^c=a.
b is called the base and c is called the exponent.
Commonly log(n) means base 10 or (in computer science) base 2. Almost always lg(n) means base 2 and ln(n) means base e.

Theorem: Let a, b, and c be positive real numbers. In the following log means base 2. Though this is not needed, any base would do.

log(ac) = log(a)+log(c)
log(a/c) = log(a) - log(c)
log(a^c) = c log(a)
log_c(a) = (log(a))/log(c): consider a = c^log_ca and take log of both sides.
c^log(a) = a ^log(c): take log of both sides.
(b^a)^c = b^ac
b^ab^c = b^a+c
b^a/b^c = b^a-c

Examples

log(2nlog(n)) = 1 + log(n) + log(log(n)) is Θ(log(n))
log(log(sqrt(n))) = log(.5log(n)) = log(.5)+log(log(n)) = -1 + log(log(n)) = Θ(log(log(n))
log(2ⁿ) = n = 2^log(n)

Floor and Ceiling

Floor: ⌊x⌋ is the greatest integer not greater than x.

Ceiling: ⌈x⌉ is the least integer not less than x.

Examples:

⌊5⌋ = ⌈5⌉ = 5
⌊5.2⌋ = 5 and ⌈5.2⌉ = 6
⌊-5.2⌋ = -6 and ⌈-5.2⌉ = -5

Complexity Theorems

A few theorems give us rules that make calculating big-Oh easier.

Theorem (arithmetic): Let d(n), e(n), f(n), and g(n) be nonnegative real-valued functions of a nonnegative integer argument and assume d(n) is O(f(n)) and e(n) is O(g(n)). Then

1. ad(n) is O(f(n)) for any nonnegative a
2. d(n)+e(n) is O(f(n)+g(n))
3. d(n)e(n) is O(f(n)g(n))

Theorem (transitivity): Let d(n), f(n), and g(n) be nonnegative real-valued functions of a nonnegative integer argument and assume d(n) is O(f(n)) and f(n) is O(g(n)). Then d(n) is O(g(n)).

Theorem (special functions): (Only n varies)

If f(n) is a polynomial of degree d, then f(n) is O(n^d).
n^x is O(aⁿ) for any x>0 and a>1.
log(n^x) is O(log(n)) for any x>0
(log(n))^x is O(n^y) for any x>0 and y>0.

Efficency

"Efficiently" is usually understood to mean the minimum running time, but occasionally there will be other constraints, such as memory use, which will be paramount.

Growth of Functions: Timing Estimates

For example, we may state the upper bound O(g(n)) for the search time for an item in some data structure of size=n items.
The following table illustrates growth rates for various functions:

n	lg n	n lg n	n^1.25	n²
1	0	0	1	1
16	4	64	32	256
256	8	2,048	1,024	65,536
4,096	12	49,152	32,768	16,777,216
65,536	16	1,048,565	1,048,476	4,294,967,296
1,048,476	20	20,969,520	33,554,432	1,099,301,922,576
16,775,616	24	402,614,784	1,073,613,825	281,421,292,179,456

A growth rate of O(lg n) occurs for algorithms similar to the binary search. The lg (logarithm, base 2) function increases by one when n is doubled.

If the values in the table represented microseconds, then a O(lg n) algorithm may take 20 microseconds to process 1,048,476 items, a O(n^1.25) algorithm might take 33 seconds, and a O(n²) algorithm might take up to 12 days!