Ch-3 Algorithm

Word Table

The Growth of Functions

asymptotic running time is the number of operation used by the algorithm as the input size approaches infinity

Big-O notation

Let \(f\) and \(g\) be functions from \(\mathrm{Z}\) (or \(\mathrm{R}\)) to \(\mathrm{R}\) , we say that \(f(x)\) is \(O(g(x))\) if there are constants \(C\) and \(k\) such that \(|f(x)|\leq C|g(x)|\) whenever \(x>k\)

Big-Omega notation

Let \(f\) and \(g\) be functions from \(\mathrm{Z}\) (or \(\mathrm{R}\)) to \(\mathrm{R}\) , we say that \(f(x)\) is \(\Omega(g(x))\) if there are constants \(C\) and \(k\) such that \(|f(x)|\geq C|g(x)|\) whenever \(x>k\)

Big-Theta notation

Let \(f\) and \(g\) be functions from \(\mathrm{Z}\) (or \(\mathrm{R}\)) to \(\mathrm{R}\) , we say that \(f(x)\) is \(\Theta(g(x))\) if \(f(x)\) is \(O(g(x))\) and \(f(x)\) is \(\Omega(g(x))\) ,there are constants \(C_1,C_2\) and \(k\) such that \(0\leq C_1g(x)\leq f(x)\leq C_2g(x)\) whenever \(x>k\)

Complexity Table