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_1$ and $c_2$ such that for $n$ big enough we have

  $$0 \ \ \leq \ \ c_1 \ \ g(n) \ \ \leq \ \ f(n) \ \ \leq \ \ c_2 \ \ g(n).$$ (2)

  
  

• 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_2$ such that for $n$ big enough we have

  $$0 \ \ \leq \ \ f(n) \ \ \leq \ \ c_2 \ \ g(n).$$ (3)

  
  

• 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_1$ such that for $n$ big enough we have

  $$0 \ \ \leq \ \ c_1 \ \ g(n) \ \ \leq \ \ f(n).$$ (4)

  
  

Let us give some examples.

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

  $$c_1 \, n^2 \ \ \leq \ \ \frac{1}{2} n^2 -3n \ \ \leq \ \ c_2 \, n^2.$$ (5)

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

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

  
  
  Indeed we have

  $$\frac{1}{2} (f(n) + g(n)) \ \ \leq \ \ max(f(n),g(n)) \ \ \leq \ \ (f(n) + g(n)).$$ (7)

  
  

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

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

  
  
  Indeed for $n \geq a$ we have

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

  
  
  Hence we can choose $c_1 = 1$ and $c_2 = 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) \in {\cal O}(g(n)) \ \iff g(n) \in {\Omega}(f(n)).$$ (10)

  
  

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) + {\Theta}(g(n))$$ (11)

means

$$f(n) - h(n) \in {\Theta}(g(n)).$$ (12)

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

$${\Sigma}_{k=1}^{k=n} \, {k} \ \in \ {\Theta}(n^2).$$ (13)