Next: The complexity of divide-and-conquer algorithms Up: A review of complexity notions Previous: A review of complexity notions

## Orders of magnitude

Let f, g et h be functions from to
• We say that g(n) is in the ORDER OF MAGNITUDE of f (n) and we write f (n) (g(n)) if there exist two (strictly) positive constants c1 and c2 such that for n big enough we have

 0    c1  g(n)    f (n)    c2  g(n). (1)

• We say that g(n) is an ASYMPTOTIC UPPER BOUND of f (n) and we write f (n) (g(n)) if there exists a (strictly) positive constants c2 such that for n big enough we have

 0    f (n)    c2  g(n). (2)

• We say that g(n) is an ASYMPTOTIC LOWER BOUND of f (n) and we write f (n) (g(n)) if there exists a (strictly) positive constants c1 such that for n big enough we have

 0    c1  g(n)    f (n). (3)

Let us give some examples.
• With f (n) = n2 - 3n and g(n) = n2 we have f (n) (g(n)). Indeed we have

 c1 n2    n2 - 3n    c2 n2. (4)

for n 12 with c1 = and c2 = .
• Assume that there exists a positive integer n0 such that f (n) > 0 and g(n) > 0 for every n n0. Then we have

 max(f (n), g(n)) (f (n) + g(n)). (5)

Indeed we have

 (f (n) + g(n))    max(f (n), g(n))    (f (n) + g(n)). (6)

• Assume a and b are positive real constants. Then we have

 (n + a)b (nb). (7)

Indeed for n a we have

 0    nb    (n + a)b    (2n)b. (8)

Hence we can choose c1 = 1 and c2 = 2b.
We have the following properties.
• f (n) (g(n)) holds iff f (n) (g(n)) and f (n) (g(n)) hold together.
• Each of the predicates f (n) (g(n)), f (n) (g(n)) and f (n) (g(n)) define a reflexive and transitive binary relation among the -to- functions. Moreover f (n) (g(n)) is symmetric.
• We have the following TRANSPOSITION FORMULA

 f (n) (g(n)) g(n) (f (n)). (9)

In practice is replaced by = in each of the expressions f (n) (g(n)), f (n) (g(n)) and f (n) (g(n)). Hence, the following

 f (n) = h(n) + (g(n)) (10)

means

 f (n) - h(n) (g(n)). (11)

Let us give another fundamental example. Let p(n) be a (univariate) polynomial with degree d > 0. Let ad be its leading coefficient and assume ad > 0. Then we have
(1)
if k d then p(n) (nk),
(2)
if k d then p(n) (nk),
(3)
if k = d then p(n) (nk).
Exercise: Prove the following

 k   (n2). (12)

Next: The complexity of divide-and-conquer algorithms Up: A review of complexity notions Previous: A review of complexity notions
Marc Moreno Maza
2003-06-06