---
tags: Algorithm
---
# Types of Order Example
- $g(n)$: your algorithm

- $f(n)$: the complexity

## Big O Order (Upper Bound)
- **Definition:**
- For a given complexity function $f(n)$, $O(f(n))$ is the set of complexity functions $g(n)$ for which there exists some positive real constant $c$ and some nonnegative integer $N$ such that for all $n ≥ N$,
$$
g(n) \le c \times f(n)
$$

- **Example**
:::info
**Ex1.7**
We show that $5n^2 \in O(n^2)$. Because, for $n \ge 0$,
$$
5n^2 \le 5n^2,
$$
we can take ***c=5*** and ***N=0*** to obtain our desired result.
:::
:::info
**Ex1.8**
Recall that the time complexity of Algorithm 1.3 (Exchange Sort) is given by
$$
T(n)=\frac{n(n-1)}{2}.
$$
Because,for $n\ge0$,
$$
\frac{n(n-1)}{2}\le\frac{n(n)}{2}=\frac{1}{2}n^2,
$$
we can take ***c=1/2*** and ***N=0*** to conclude that $T(n) \in O(n^2)$.
:::
:::info
**Ex1.9**
We show that $n^2 + 10n \in O(n^2)$.Because, for $n \ge 1$,
$$
n^2+10n \le n^2 + 10n^2 = 11n^2,
$$
we can take ***c=11*** and ***N=1*** to obtain our result.
:::
:::info
**Ex1.10**
We show that $n^2 \in O(n^2+10n)$.Because, for $n \ge 0$,
$$
n^2 \le 1 \times (n^2 + 10n),
$$
we can take ***c=1*** and ***N=0*** to obtain our result.
:::
:::info
**Ex1.11**
We show that $n \in O(n^2)$. Because, for $n \ge 1$,
$$
n \le 1 \times n^2,
$$
we can take ***c=1*** and ***N=1*** to obtain our result.
:::
## $\Omega$ Omega Order (Lower Bound)
- **Definition:**
$$
g(n) \ge c \times f(n)
$$

- **Examples**
:::info
**Ex1.12**
We show that $5n^2 \in \Omega(n^2)$. Because, for $n \ge 0$,
$$
5n^2 \ge 1 \times n^2,
$$
we can take ***c=1*** and ***N=0*** to obtain our result.
:::
:::info
**Ex1.13**
We show that $n^2 + 10n \in \Omega(n^2)$. Because, for $n \ge 0$,
$$
n^2 + 10n \ge n^2,
$$
we can take ***c=1*** and ***N=0*** to obtain our result.
:::
:::info
**Ex1.14**
Consider again the time complexity of Algorithm 1.3 (Exchange Sort). We show that
$$
T(n) = \frac{n(n-1)}{2} \in \Omega(n^2).
$$
For $n \ge 2$,
$$
n-1 \ge \frac{n}{2}.
$$
Therefore, for $n \ge 2$,
$$
\frac{n(n-1)}{2} \ge \frac{n}{2} \times \frac{n}{2} = \frac{1}{4}n^2,
$$
which mean we can take ***c=1/4*** and ***N=2*** to obtain our result.
:::
:::info
**Ex1.15**
We show that $n^3 \in \Omega(n^2)$. Because, if $n \ge 1$,
$$
n^3 \ge 1 \times n^2,
$$
we can take ***c=1*** and ***N=1*** to obtain our result.
:::
## $\Theta$ Theta Order (Exact Order)
- **Definition:**
$$
\Theta(f(n))=O(f(n)) \cap \Omega(f(n)) \\
c \times f(n) \le g(n) \le d \times f(n)
$$

- **Example**
:::info
**Ex1.16**
Consider once more the time complexity of Algorithm 1.3. Example 1.18 and 1.14 together establish that
$$
T(n) = \frac{n(n-1)}{2}\ {is\ in\ both} O(n^2)\ and\ \Omega(n^2).
$$
This means that $T(n) \in O(n^2) \cap \Omega(n^2)$
:::
:::info
**Ex1.17**
We show that $n$ is not in $Ω(n^2)$ by using proof by contradiction.
In this type of proof we assume something is true in this case, that $n ∈ Ω(n^2)$ and then we do manipulations that lead to a result that is not true. That is, the result contradicts something known to be true. We then conclude that what we assumed in the first place cannot be true.

Assuming that $n ∈ Ω(n^2)$ means we are assuming that there exists some positive constant $c$ and some nonnegative integer $N$ such that, for $n ≥ N$,
$$
n ≥ cn^2
$$
If we divide both sides of this inequality by $cn$, we have, for $n ≥ N$,
$$
\frac{1}{c} ≥ n
$$
However, for any $n > \frac{1}{c}$, this inequality cannot hold, which means that it cannot hold for all $n ≥ N$. This contradiction proves that $n$ is not in $Ω(n^2)$.

We have one more definition concerning order that expresses relationships such as the one between the function $n$ and the function $Ω(n^2)$.

    ----------|----------------------------------|----------------------------------
              N              成立                1/c             不成立
    
    條件 n >= N, n <= 1/c，但是 n > 1/c 應要是不成立的，但若不成立就違反 n >= N 的條件。

:::

## Small o Order (Strong Upper Bound)
- **Definition:**
- For a given complexity function *f(n)*, *o(f(n))* is the set of all complexity functions *g(n)* satisfying the following: For every positive real constant *c* there exists a nonnegative integer N such that, for all $n \ge N$,
$$
g(n) \le c \times f(n).
$$

- **Examples**
:::info
**Ex1.18**
We show that
$$
n \in o(n^2).
$$
Let c > 0 be given. We need to find an *N* such that, for $n \ge N$,
$$
n \le cn^2.
$$
If we divide both sides of this inequality by cn, we get
$$
\frac{1}{c} \le n.
$$
Therefore, it suffices to choose any $N \ge \frac{1}{c}$.
Notice that the value of *N* depends on the constant c. For example, if c=0.00001, we must take *N* equal to at least 100,000. Thst is, for
$$
n \le 0.00001n^2
$$
:::
:::info
**Ex1.19**
We show that *n* is not in o(5n). We will use proof by contradiction to show this.
Let $c = \frac{1}{6}$. If $n \in o(5n)$, then there must exist some *N* such that, for $n \ge N$,
$$
n \le \frac{1}{6}5n = \frac{5}{6}n.
$$
This contradiction proves that n is not in o(5n).
:::