Elvin Yung
Stuff on proofs.
-
$\Theta(1)$ is constant time. -
$\Theta(log n)$ is logarithmic time. -
$\Theta(n)$ is linear time. -
$\Theta(n log n)$ is pseudolinear time, which is also called sorting time. -
$\Theta(n^2)$ is quadratic time. -
$\Theta(n^3)$ is cubic time. -
$\Theta(2^n)$ is exponential time. -
$\Theta(n^k)$ is polynomial time. -
Textbooks usually emphasize that polynomial time is good. In practice, cubic and quadratic are both fairly inefficient, while pseudolinear and logarithmic are usually much better.
-
You should always keep in mind the size of the input for the particular problem. If
$f(x) \in O(g(x))$ , but the intersection point is sufficiently large, it might still be better to use the solution that runs at$g(x)$ if the input size will be mostly sufficiently small.
- Let
$f(n) > 0, g(n) > 0$ for all$n \geq n_0$ . - Suppose that
$L = \lim_{n \rightarrow \infty} \frac {f(n)} {g(n)}$ . - Then:
- If
$L=0$ ,$f(n) \in o(g(n))$ . - If
$0 < L < \infty$ ,$f(n) \in \Theta(g(n))$ . - If
$L < \infty$ ,$f(n) \in w(g(n))$ .
- If
$f(n) = \Theta(g(n)) \Leftrightarrow g(n) = \Theta(f(n))$ $f(n) = O(g(n)) \Leftrightarrow g(n) = \Omega(f(n))$ $f(n) = o(g(n)) \Leftrightarrow g(n) = \omega(f(n))$ $f(n) = \Theta(g(n)) \Leftrightarrow g(n) = \Omega(f(n)) \land f(n) = \Omega$ $f(n) = o(g(n)) \Rightarrow g(n) = O(g(n))$ $f(n) = o(g(n)) \Rightarrow f(n) \neq \Omega(g(n))$ $f(n) = w(g(n)) \Rightarrow f(n) neq \Omega(g(n))$ $f(n) = w(g(n)) \Rightarrow f(n) \neq O(g(n))$
- Given an algorithm, obtain the growth order of its running time.
More stuff on stuff