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

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

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

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

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

Let us give some examples.

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

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

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

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

Indeed we have

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

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

Indeed for n $\geq$ a we have

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

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

We have the following properties.

f (n) $\in$ $\Theta$ (g(n)) holds iff f (n) $\in$ $\cal {O}$ (g(n)) and f (n) $\in$ $\Omega$ (g(n)) hold together.
Each of the predicates f (n) $\in$ $\Theta$ (g(n)), f (n) $\in$ $\cal {O}$ (g(n)) and f (n) $\in$ $\Omega$ (g(n)) define a reflexive and transitive binary relation among the $\mathbb {N}$ -to- $\mathbb {R}$ functions. Moreover f (n) $\in$ $\Theta$ (g(n)) 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)). (9)

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

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

(10)

means

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

(11)

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

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

Exercise: Prove the following

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

(12)

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

Marc Moreno Maza
2004-04-27