## Computation Complexity

In study of algorithms or algorithmics we prove by giving and analyzing an
algorithm that can be solved in a O(f(n)) time for some function f(n) that we
try to reduce as much as possible. On other hand, in complexity theory, we try
to find a function g(n) as large as possible for which we prove that any
algorithm solves problem on all its in Ω(g(n)) function g(n) is called lower
bound on the complexity of the problem.

The principle techniques and concepts

- Information-theoretic Argument
- Adversary Argument
- Reduction
- NP-Completeness