Time Complexity

Time complexity $T(n)$ as a function of input length $n$

Asymptotic notation #

FunctionIs 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 $

1$g$ grows faster$O(n^{\log_b a - \epsilon})$, $\epsilon > 0$$\Theta(n^{\log_b a}))$
2same 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