Orders of magnitude

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 mathend000#, g mathend000# et h mathend000# be functions from $\mathbb {N}$ mathend000# to $\mathbb {R}$ mathend000#

We say that g(n) mathend000# is in the ORDER OF MAGNITUDE of f (n) mathend000# and we write f (n) $\in$ $\Theta$ (g(n)) mathend000# if there exist two (strictly) positive constants c₁ mathend000# and c₂ mathend000# such that for n mathend000# big enough we have

0 $\displaystyle \leq$ c₁ g(n) $\displaystyle \leq$ f (n) $\displaystyle \leq$ c₂ g(n). (2)
We say that g(n) mathend000# is an ASYMPTOTIC UPPER BOUND of f (n) mathend000# and we write f (n) $\in$ $\cal {O}$ (g(n)) mathend000# if there exists a (strictly) positive constants c₂ mathend000# such that for n mathend000# big enough we have

0 $\displaystyle \leq$ f (n) $\displaystyle \leq$ c₂ g(n). (3)
We say that g(n) mathend000# is an ASYMPTOTIC LOWER BOUND of f (n) mathend000# and we write f (n) $\in$ $\Omega$ (g(n)) mathend000# if there exists a (strictly) positive constants c₁ mathend000# such that for n mathend000# big enough we have

0 $\displaystyle \leq$ c₁ g(n) $\displaystyle \leq$ f (n). (4)

Let us give some examples.

With f (n) = ${\frac{{1}}{{2}}}$ n² - 3n mathend000# and g(n) = n² mathend000# we have f (n) $\in$ $\Theta$ (g(n)). mathend000# Indeed we have

c₁ n² $\displaystyle \leq$ $\displaystyle {\frac{{1}}{{2}}}$ n² -3n $\displaystyle \leq$ c₂ n². (5)

for n $\geq$ 12 mathend000# with c₁ = ${\frac{{1}}{{4}}}$ mathend000# and c₂ = ${\frac{{1}}{{2}}}$ mathend000#.
Assume that there exists a positive integer n₀ mathend000# such that f (n) > 0 mathend000# and g(n) > 0 mathend000# for every n $\geq$ n₀ mathend000#. Then we have

max(f (n), g(n)) $\displaystyle \in$ $\displaystyle \Theta$ (f (n) + g(n)). (6)

Indeed we have

$\displaystyle {\frac{{1}}{{2}}}$ (f (n) + g(n)) $\displaystyle \leq$ max(f (n), g(n)) $\displaystyle \leq$ (f (n) + g(n)). (7)
Assume a mathend000# and b mathend000# are positive real constants. Then we have

(n + a)^b $\displaystyle \in$ $\displaystyle \Theta$ (n^b). (8)

Indeed for n $\geq$ a mathend000# we have

0 $\displaystyle \leq$ n^b $\displaystyle \leq$ (n + a)^b $\displaystyle \leq$ (2n)^b. (9)

Hence we can choose c₁ = 1 mathend000# and c₂ = 2^b mathend000#.

We have the following properties.

f (n) $\in$ $\Theta$ (g(n)) mathend000# holds iff f (n) $\in$ $\cal {O}$ (g(n)) mathend000# and f (n) $\in$ $\Omega$ (g(n)) mathend000# hold together.
Each of the predicates f (n) $\in$ $\Theta$ (g(n)) mathend000#, f (n) $\in$ $\cal {O}$ (g(n)) mathend000# and f (n) $\in$ $\Omega$ (g(n)) mathend000# define a reflexive and transitive binary relation among the $\mathbb {N}$ mathend000#-to- $\mathbb {R}$ mathend000# functions. Moreover f (n) $\in$ $\Theta$ (g(n)) mathend000# is symmetric.
We have the following TRANSPOSITION FORMULA

f (n) $\displaystyle \in$ $\displaystyle \cal {O}$ (g(n)) $\displaystyle \iff$ g(n) $\displaystyle \in$ $\displaystyle \Omega$ (f (n)). (10)

In practice $\in$ mathend000# is replaced by = mathend000# in each of the expressions f (n) $\in$ $\Theta$ (g(n)) mathend000#, f (n) $\in$ $\cal {O}$ (g(n)) mathend000# and f (n) $\in$ $\Omega$ (g(n)) mathend000#. Hence, the following

f (n) = h(n) + $\displaystyle \Theta$ (g(n))

(11)

means

f (n) - h(n) $\displaystyle \in$ $\displaystyle \Theta$ (g(n)).

(12)

Let us give another fundamental example. Let p(n) mathend000# be a (univariate) polynomial with degree d > 0 mathend000#. Let a_d mathend000# be its leading coefficient and assume a_d > 0 mathend000#. Then we have

(1) mathend000#: if k $\geq$ d mathend000# then p(n) $\in$ $\cal {O}$ (n^k) mathend000#,
(2) mathend000#: if k $\leq$ d mathend000# then p(n) $\in$ $\Omega$ (n^k) mathend000#,
(3) mathend000#: if k = d mathend000# then p(n) $\in$ $\Theta$ (n^k) mathend000#.

Exercise: Prove the following

$\displaystyle \Sigma_{{{k=1}}}^{{{k=n}}}$ k $\displaystyle \in$ $\displaystyle \Theta$ (n²).

(13)

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

Marc Moreno Maza
2007-01-10