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

CaseExplanation$f(n)$$T(n) 1g grows fasterO(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) 3f 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