Algorithms review 1 Runtime Complexity

Posted on In

This is a personal notes of algorithms courses

Definition#

  1. We measure the run time of an algorithm by counting the number of steps and therefore define an algorithmic complexity as a numerical function T(n), where n is the input size.
  2. Constant time means the time is independent of the input size
  3. We measure the runtime of an algorithm using $\Theta$,$\Omega$,O

Upper Bound (Big-O)#

For any monotonic functions with two positive number f, g,we say $f(n) = O(g(n))$[or $f(n)\in O(g(n))$ if $g(n)$ eventually dominates $f(n)$]. Formally, there exists a positive real number $c>0$, and a real number, $n_0$, such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$. (To be simple, when $n$ goes infinity, $f(n)$ is smaller or equal than $g(n)$) or we called $g(n)$ is upper bound of $f(n)$.

Lower Bound (Big-Omega)#

For any monotonic functions with two positive numbers f, g,we say $f(n) = \Omega(g(n))$[or $f(n)\in \Omega(g(n))$ if $f(n)$ eventually dominates $g(n)$]. Formally, there exists a positive real number $c>0$, and a real number, $n_0$, such that $f(n) \geq c \cdot g(n)$ for all $n \geq n_0$. (To be simple, when $n$ goes infinity, $f(n)$ is greater or equal than $g(n)$)

Exact Bound (Big-Theta)#

For any monotonic functions with two positive numbers f, g,we say $f(n) = \Theta(g(n))$[or $f(n)\in \Theta(g(n))$ if $f(n) = \Omega(g(n))$ and $f(n) = O(g(n))$]. Formally, there exists two positive real number $c_1$ and $c_2$, and a real number, $n_0$, such that $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$ for all $n \geq n_0$. (To be simple, when $n$ goes infinity, $f(n)$ has the same increasing rate with $g(n)$)

Lower Bound for Sorting#

For any sorting based on comparison we must take at least($\Omega(n\log(n))$)to sort an array of n elements in the worst case. A decision tree model was introducted to illustrate this model.
Decision Tree

Suppose we have input size = n, Now we have 6 leaves in this decision tree which can represent as $n!$. If we make it as a Full Binary Tree, the number of leaves becomes $2^h$ where h represents its height. Hence, $2^h \geq n!$, after taking log on both sides, $h \geq\log(n!)$. Since h(the height of decision tree) represents the number of comparisons in a sorting algorithm, so $T(n) = h \geq \log(n!)$. To simplify $\log(n!)$:
$$\log(n!) = \log(n(n-1)(n-2)…1)$$
$$\log(n!) \geq \log(n(n-1)(n-2)…(n-n/2))$$
$$\log(n!) \geq \log((n/2)^{n/2}) = \Omega(n \cdot \log(n))$$

Some tips to compare time complexity#

Example 1#

Arrange the following functions in increasing order of growth rae with $g(n)$ gollowing $f(n)$ in your list if and only if f(n) = $O(g(n))$

$\log{n^n}$, $n^2$,$n^{\log n}$,$n\log\log{n}$,$2^{\log{n}}$,$\log^2{n}$,$n^{\sqrt{2}}$

Tips:

  • $2^{\log{n}}$ = $n$
  • $\log{n^n}$ = $n\cdot\log{n}$
  • TRICK: set n = 1024

Example 2#

Suppose that f(n) and g(n) are two positive non-dereasing functions such that $f(n) = O(g(n))$, Is it true that $2^{f(n)} = O(2^{g(n)})$ ?

Tip : Suppose $f(n) = 2n$ and $g(n) = n$.

Example 3#

Arrange the following functions in increasing order of growth rae with $g(n)$ gollowing $f(n)$ in your list if and only if f(n) = $O(g(n))$

$4^{\log n}$,$\sqrt{\log n}$,$n^{\log\log n}$,$(\sqrt{2})^{\log n}$,$2^{2\sqrt{\log n}}$,$n^{1/\log{n}}$,$(\log{n})!$

Tips:

  • $\because$ $a^{\log_a{N}} = N$ $\And$ $(a^m)^n = a^{mn} = {a^n}^m$

    $\therefore$ $4^{\log n} = n^2$

  • $\because$ $\log_a{N} = \frac{\log_m{N}}{\log_m{a}}$

    $\therefore$ $\log_{a^m}{b^n} = \frac{n}{m}\log_a{b}$ $\And$ $\log_a{b} = \frac{1}{\log_b{a}}$

    $\therefore$ $n^{1/\log{n}} = n^{log_n{2}} = 2$

  • $\because$ $n! = \sqrt{2\pi{n}}(\frac{n}{e})^n$

    $\therefore$ $n! = O(\sqrt{n}\cdot{n^n})$

    $\therefore$ $(\log{n})! = O(\sqrt{\log{n}}\cdot(\log n)^{\log n})$

  • Set $\log{n} = t$

    $n^{\log\log n} = n^{\log t} = n^{\frac{\log_n{t}}{\log_n{2}}} = (n^{log_n{t}})^\frac{1}{\log_n{2}} = t^\frac{1}{log_n{2}} = (\log{n})^{\log{n}}$

Example 4#

Suppose that f(n) and g(n) are two positive non-dereasing functions such that $f(n) = \Omega(g(n))$, Is it true that $2^{f(n)} = \Omega(2^{g(n)})$ ?

Tip : Suppose $f(n) = n$ and $g(n) = 5n$.

Reference#

[1] Algorithms in Action, by V. Savvich, First Edition, 2019.