Definitions

$\theta(g(n)) = \{\, f(n) \mid \text{there exists positive constants } c_1, c_2 \text{ and } n_0 \text{ such that } 0 \le c_1g(n) \le f(n) \le c_2g(n) \text{ for all } n \ge n_0 \, \}$

$O(g(n)) = \{\, f(n) \mid \text{there exists positive constants } c \text{ and } n_0 \text{ such that } 0 \le f(n) \le cg(n) \text{ for all } n \ge n_0 \, \}$

$o(g(n)) = \{\, f(n) \mid \text{for any positive constant } c > 0 \text{ there exists a constant } n_0 >0 \text{ such that } 0 \le f(n) \lt cg(n) \text{ for all } n \ge n_0 \, \}$

$\Omega(g(n)) = \{\, f(n) \mid \text{there exists positive constants } c \text{ and } n_0 \text{ such that } 0 \le cg(n) \le f(n) \text{ for all } n \ge n_0 \, \}$

$\omega(g(n)) = \{\, f(n) \mid \text{for any positive constant } c > 0 \text{ there exists a constant } n_0 >0 \text{ such that } 0 \le cg(n) \lt f(n) \text{ for all } n \ge n_0 \, \}$

How to Interpret Asymptotic Notations in Equations

Rule 1: When the asymptotic notation stands alone on the right side of an equation or inequality, equal sign means set membership.

Example: $n = O(n^2)$ means $n \in O(n^2)$.

Rule 2: In general, when asymptotic notation appears in a formula, we interpret it as standing for some anonymous function that we do not care to name.

Example: $2n^2 + 3n + 1 = 2n^2 + \theta(n)$ means that $2n^2 + 3n + 1 = 2n^2 + f(n)$, where $f(n)$ is some function in the set $\theta(n)$ (in this case $f(n) = 3n + 1$).

Example: $T(n) = 2T(n/2) + \theta(n)$.

Rule 3: The number of anonymous functions in an expression is equal to the number of times the asymptotic notations appears.

Example: in $\sum_{i=0}^n O(i)$, there is only a single anonymous function. This is not the same as $O(1) + O(2) + \cdots + O(n)$, which doesn’t have a clear interpretation.

Rule 4: When the asymptotic notation appears on the left side of an equation or inequality, we interpret it as: No matter how the anonymous functions are chosen on the left side, there is a way to choose the anonymous functions on the right side to make the equation valid.

Example: $2n^2 + \theta(n) = \theta(n^2)$.

Rules

Transitivity:

$f(n) = \theta(g(n))$ and $g(n) = \theta(h(n)) \Rightarrow f(n) = \theta(h(n))$

$f(n) = O(g(n))$ and $g(n) = O(h(n)) \Rightarrow f(n) = O(h(n))$

$f(n) = \Omega(g(n))$ and $g(n) = \Omega(h(n)) \Rightarrow f(n) = \Omega(h(n))$

$f(n) = o(g(n))$ and $g(n) = o(h(n)) \Rightarrow f(n) = o(h(n))$

$f(n) = \omega(g(n))$ and $g(n) = \omega(h(n)) \Rightarrow f(n) = \omega(h(n))$

Reflexivity:

$f(n) = \theta(f(n))$

$f(n) = O(f(n))$

$f(n) = \Omega(f(n))$

Symmetry:

$f(n) = \theta(g(n))$ if and only if $g(n) = \theta(f(n))$

Related Theorem:

$f(n) = \theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

Transpose Symmetry:

$f(n) = O(g(n))$ if and only if $g(n) = \Omega(f(n))$

$f(n) = o(g(n))$ if and only if $g(n) = \omega(f(n))$

Trichotomy:

For any two real numbers $a$ and $b$, exactly one of the following must hold: \(a < b, a = b, a > b\).

However, not all functions are asymptotically comparable. That is, for two functions $f(n)$ and $g(n)$, it may be the case that neither $f(n) = O(g(n))$ nor $f(n) = \Omega(g(n))$ holds.

Example: $f(n) = n, g(n) = n^{1 + \sin n}$.

Examples

Example:

Let $f_1(n) = \theta(g_1(n))$ and $f_2(n) = \theta(g_2(n))$ be asymptotically nonnegative. Prove or disprove the following:

  1. $f_1(n) + f_2(n) = \theta\left(g_1(n) + g_2(n)\right)$
  2. $f_1(n) - f_2(n) = \theta\left(g_1(n) - g_2(n)\right)$
  3. $f_1(n) \cdot f_2(n) = \theta\left(g_1(n) \cdot g_2(n)\right)$
  4. $\frac{f_1(n)}{f_2(n)} = \theta\left(\frac{g_1(n)}{g_2(n)}\right)$.

Proof: By the definition of $\theta$ we have:

\[\begin{align} 0 \le c_1g_1(n) \le f_1(n) \le c_2g_1(n) \text{ for all } n \ge n_1 \tag{1} \\ 0 \le d_1g_2(n) \le f_2(n) \le d_2g_2(n) \text{ for all } n \ge n_2 \tag{2} \end{align}\]

1): $(1)+(2)$ gives

\[\begin{align} c_1g_1(n) + d_1g_2(n) &\le f_1(n)+f_2(n) \le c_2g_1(n) + d_2g_2(n) &\text{ for all } n \ge max(n_1, n_2) \\ min(c_1, d_1)(g_1(n)+g_2(n) & \le f_1(n)+f_2(n) \le max(c_2, d_2)(g_1(n)+g_2(n)) &\text{ for all } n \ge max(n_1, n_2) \end{align}\]

So $f_1(n) + f_2(n) = \theta\left(g_1(n) + g_2(n)\right)$

2): An counter examples would be:

\[\begin{align} f_1(n) &= 2n \\ f_2(n) &= n + 1 \\ g_1(n) &= n +1 \\ g_2(n) &= n \end{align}\]

Note:

The relation would holf if $g_1(n) = o(g_2(n))$

Intuitively, this fails because after $(1) - (2)$ we cannot guarantee that LHS and RHS are both positive.

3): $(1) \times (2)$ and the result follows trivially.

4): $(1) \div (2)$ and the result follows trivially.

Example:

Let $f(n)$ and $g(n)$ be positive non-decreasing functions such that $f(n) - g(n) = \theta(1)$. Prove $f(n) = \theta(g(n))$.

Proof:

By definition we have

\[0 \le c_1 \le f(n) - g(n) \le c_2 \quad \text{ for all } n \ge n_0 \ge 0\]

First prove the LHS.

\[\begin{align} f(n) &\ge g(n) + c_1 &&\text{[ add } g(n) \text{ to both sides ]} \\ &\ge g(n) &&\text{[ } c_1 \text{ positive ]} \\ \end{align}\]

Now on the RHS.

\[\begin{align} f(n) &\le g(n) + c_2 \\ &= \left(\frac{c_2}{g(n)} + 1\right)g(n) \\ &\le \left(\frac{c_2}{g(1)} + 1\right)g(n) && \text{ [ } g(n) \text{ non-desreasing ]} \end{align}\]

Intuitively, because $g(n)$ is non-decreasing, eventually the constant $c_2$ becomes a non-factor, so we basically have $f(n) \le g(n)$.

Example:

Let $f(n)$ and $g(n)$ be asymptotically nonnegative functions. Prove that $max(f(n), g(n)) = \theta(f(n) + g(n))$.

Proof:

choose $n_0$ such that for all $n \ge n_0, f(n)$ and $g(n)$ are nonnegative. Then:

\[\begin{align} max(f(n), g(n)) & \le f(n) + g(n) &&\text{[ $f(n)$ and $g(n)$ are nonnegative]} \\ 2max(f(n), g(n)) & \ge f(n) + g(n) &&\text{[property of max()]} \end{align}\]

Thus we have

\[\frac{1}{2}(f(n) + g(n)) \le max(f(n), g(n) \le f(n) + g(n) \text{ for all } n \ge n_0\]

, which is the definition of $\theta(f(n) + g(n))$ with $c_1 = \frac{1}{2}$ and $c_2 = 1$.

Example:

Let $f(n)$ and $g(n)$ be positive functions. Prove that $min(f(n), g(n)) = \theta\left(\frac{f(n)g(n)}{f(n)+g(n)}\right)$.

Proof:

Two handy properties:

  1. $max(f(n), g(n)) \le f(n) + g(n) \le 2max(f(n), g(n))$
  2. $f(n)*g(n) = max(f(n), g(n)) * min(f(n), g(n))$

Notice that

\[\begin{align} \left(\frac{f(n)g(n)}{f(n)+g(n)}\right) & = \left(\frac{max(f(n), g(n))min(f(n), g(n))}{f(n)+g(n)}\right) && \text{[ by property 2 ]} \\ & = \left(\frac{max(f(n), g(n))}{f(n)+g(n)}\right)min(f(n), g(n)) \\ & \le \left(\frac{f(n)+g(n)}{f(n)+g(n)}\right)min(f(n),g(n)) && \text{[ by property 1 ]} \\ & = min(f(n), g(n)) \end{align}\]

Similarly,

\[\begin{align} \left(\frac{f(n)g(n)}{f(n)+g(n)}\right) & = \left(\frac{max(f(n), g(n))}{f(n)+g(n)}\right)min(f(n), g(n)) \\ & \ge \left(\frac{\frac{1}{2}(f(n)+g(n))}{f(n)+g(n)}\right)min(f(n),g(n)) && \text{[ by property 1 ]} \\ & = \frac{1}{2}min(f(n), g(n)) \end{align}\]

Thus we have

\[\begin{align} \left(\frac{f(n)g(n)}{f(n)+g(n)}\right) & = \theta(min(f(n), g(n)) &&\text{[ by definition of } \theta \text{ ]}\\ min(f(n), g(n)) & = \theta\left(\frac{f(n)g(n)}{f(n)+g(n)}\right) &&\text{[ by symmetry of } \theta \text{ ]} \end{align}\]