2 - Analysis of Algorithms

1. Common Order-of-growth Classifications

  • 1,logN,NlogN,N2,N3, and 2N1, \log{N}, N \log{N}, N^2, N^3, \text{ and } 2^N
    • order of growth discards leading coefficient
    • time=lgT(N)\text{time} = \lg{T(N)}
    • size=lgN\text{size} = \lg{N}

2. Theory of Algorithms

3. Why Big-Oh Notation ? // TODO

  • Formal Definition: T(n)=O(f(n))T(n) = O(f(n)) if and only if there exist constants c,n0>0c,n_0 > 0 such that T(n)cf(n)T(n) \le c \cdot f(n) for all nn0n \ge n_0
    • T(n)T(n) is the function of the running time of an algorithm.
    • Warning c,n0c, n_0 cannot depend on n.
  • [NOTE] It kinds of says, we use nkn^k, but not nk1n^{k-1}
    • Because O(nk1)=cnk1O(n^{k-1}) = c \cdot n^{k-1} will always less then nkn^k (c is a constant, but n is not).
    • And we need that, T(n) is bounded above by a constant multiple of f(n).
  • Example

4. Words

  • asymptotic [,æsimp'tɔtik,-kəl] adj. 渐近的;渐近线的
  • ubiquitous [ju:'bikwitəs] adj. 普遍存在的;无所不在的

results matching ""

    No results matching ""