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