Algorithm Time Complexity Analysis

Published on
Updated on
Data Structure & Alogirthm
4

For function f:

f= O(g) (Big-O) means that \exists k \in \R_{0},(\exists n_0 \in \N(\forall n\in \N. (n > n_0\implies f(n)\le kg(n))))

  • we can use big-O to describe functions' upper bound by some common function where as larger input there exists suchk times the function upper the current function

  • a.k.af \le g

f = \Omega(g) (Big-Omega) means that \exists k \in \R_{>0},(\exists n_0 \in \N(\forall n\in \N. (n > n_0\implies f(n)\ge kg(n))))

  • we can use big-Omega to describe functions' lower bound by some common function where as larger input there exists suchk times the function lower the current function

  • f\ge g

f = \Theta(g) (Big-Theta) means that \exists k_1,k_2 \in \R_{>0},(\exists n_0 \in \N(\forall n\in \N. (n > n_0\implies k_1g(n)\le f(n)\le k_2g(n))))

  • There exist another function bounded function in some areak_1,k_2 as larger input

  • f=O(g) \land f = \Omega(g)\iff f = \Theta(g)

  • f\approx g

f = o(g) (Little-o) means that \forall k \in \R_{>0},(\exists n_0 \in \N(\forall n\in \N. (n > n_0\implies f(n) < kg(n))))

f = \omega(g) (Little-omega) means that \forall k \in \R_{>0},(\exists n_0 \in \N(\forall n\in \N. (n > n_0\implies f(n) > kg(n))))

Some Notices

log in time limit analysis is always stand forlog_2 and we always use\varphi to present the golden ratio

1 < log(n) < n^{0.001} < n < nlog(n) < n^{1.001} < n^{1000} < 1.001^{n} < 2^n forlim_{n\to \infty}