Time Complexity
Time complexity $T(n)$ as a function of input length $n$
Asymptotic notation #
| Function | Is like |
|---|---|
| $$f(n) = \omega(g(n))$$ | $a < b$ |
| $$f(n) = \Omega(g(n)))$$ | $a \leq b$ |
| $$f(n) = \mathcal{O}(g(n))$$ | $a \geq b$ |
| $$f(n) = o(g(n))$$ | $a > b$ |
| $$f(n) = \Theta(g(n))$$ | $a = b$ |
$$f(n) = \Theta(g(n)) \Leftrightarrow f(n)=\Omega(g(n)) \land f(n)=\mathcal{O}(g(n))$$ (like $a = b$)
Master theorem #
Solves recurrences in the form $$ T(n) = a T(n/b) + f(n)\\ $$ where $a \geq 1$ and $b > 1 $
| Case | Explanation | $f(n)$ | $T(n)$ |
|---|---|---|---|
| 1 | $g$ grows faster | $O(n^{\log_b a - \epsilon})$, $\epsilon > 0$ | $\Theta(n^{\log_b a}))$ |
| 2 | same order | $\Theta(n^{\log_b a})$ | $\Theta(n^{\log_b a} \lg n)$ |
| 3 | $f$ grows faster | $\Omega(n^{\log_b a + \epsilon})$, $\epsilon > 0$ | $\Theta(f(n))$ |
For case 3, the regularity condition also needs to hold: $a f(n/b) \leq cf(n)$ for any $c < 1$
$n^{\log_b{a}}$ is sometimes written as $g_{a,b}$
Complexity classes #
P (Polynomial) problems: solvable (and hence also verifiable) in polynomial time
NP (Non-deterministic Polynomial) problems: verifiable in polynomial time or solvable in non-deterministic polynomial time
NP-Complete: subset of NP problems in which every other problem in NP can by reduced to them in polynomial time. If a polynomial-time solution is found to any NP-Complete problem then P = NP.
NP-Hard: At least as hard as the hardest problems in NP. Not necessarily verifiable in polynomial time. The ones that are are NP-Complete (hence NP-Complete is a subset of NP-Hard)
P vs. NP #
The famous problem if P is equal to NP