Asymptotic Analysis

1. Merge Sort

   • Divide & Conquer
   • $N logN$
   • $log_2N$意義

     N/2，要除幾次才會得到1

2. Insertion Sort/Selection Sort/Bubble Sort

   • Time complexity: $N^2$
3. Worst Case Analysis
   • easy to find, more general.
4. Constant factors depends on architectures, compilers, programming implementations or even compiler optimizations. No need to precise the constants.
5. We identify Fast Algorithms as “worst-case running time grows slowly with input size”.
   • Suppress for two:
     • constant factors, too system-dependent.
     • lower order terms, irrelevant for large inputs.
6. Linear Time is some of the cases the best scenario.
7. Big-Oh ($Ο$, Upper Bound)
   • $T(n) = O( f(n) )$
   • If there exist constants $c$, $n_0>0$ , such that $T(n) ≤ c f(n)$, for all $n ≥ n_0$
8. Big Omega ($Ω$, Lower Bound)
9. Big Theta ($Θ$, sandwitch)
10. Little-Oh notation:
    • Strictly, no equal
    • $f(n) = o( g(n) )$, For all $c > 0$, there exists some $k > 0$, such that $0 ≤ f(n) < cg(n)$ for all $n ≥ k$.