# 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